#ABC303B. 不开心的摄影
不开心的摄影
题目描述
有 个人,编号为 ,一共拍摄了 张合影。每张合影中,所有人站成一排,每个人恰好出现一次。第 张照片从左到右的人员编号为 。
若两个人在所有照片中都没有相邻站立过,则称他们为一对不开心的人。照片中只有位置相差 才算相邻,队首与队尾不相邻。交换两个人的顺序视为同一对,每对由两名不同的人组成。请计算不开心的人的对数。
输入格式
第一行输入两个整数 ,分别代表人数与照片数量。
此后 行,第 行输入 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n}\left(1\leqq a_{i,j}\leqq n\right)$。保证每一行都是 的一个排列,即每个编号恰好出现一次。
输出格式
输出一个整数,代表不开心的人的对数。
测试样例
4 2
1 2 3 4
4 3 1 2
2
样例 1 解释
两张照片中曾相邻的无序对为 。总共有 对不同的人,因此还剩 与 两对,答案为 。
3 3
1 2 3
3 1 2
1 2 3
0
10 10
4 10 7 2 8 3 9 1 6 5
3 6 2 9 1 8 10 7 4 5
9 3 4 5 7 10 1 8 2 6
7 3 1 8 4 9 5 6 2 10
5 2 1 4 10 7 9 8 3 6
5 8 1 6 9 3 2 4 7 10
8 10 3 4 5 7 2 9 6 1
3 10 2 7 8 5 1 4 9 6
10 6 1 5 4 2 3 8 9 7
4 5 9 1 8 2 7 6 3 10
6