让我们将 $$$p_i(n)$$$ 定义为以下排列:$$$[i, 1, 2, \dots, i - 1, i + 1, \dots, n]$$$。这意味着第 $$$i$$$ 排列几乎是恒等排列(即将每个元素映射到其自身)排列,但元素 $$$i$$$ 位于第一个位置。示例:
- $$$p_1(4) = [1, 2, 3, 4]$$$;
- $$$p_2(4) = [2, 1, 3, 4]$$$;
- $$$p_3(4) = [3, 1, 2, 4]$$$;
- $$$p_4(4) = [4, 1, 2, 3]$$$。
给定一个数组 $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_i \le n$$$)。
令 $$$pos(p, val)$$$ 为元素 $$$val$$$ 在 $$$p$$$ 中的位置。因此,$$$pos(p_1(4), 3) = 3,pos(p_2(4), 2) = 1,pos(p_4(4), 4) = 1$$$。
让我们定义一个函数 $$$f(p) = \sum\limits_{i=1}^{m - 1} |pos(p, x_i) - pos(p, x_{i + 1})|$$$,其中 $$$|val|$$$ 是 $$$val$$$ 的绝对值。该函数表示$$$p$$$中$$$x$$$的相邻元素之间的距离之和。
您的任务是计算 $$$f(p_1(n)), f(p_2(n)), \dots, f(p_n(n))$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — 每个排列中的元素数量和 $$$x$$$ 中的元素数量。
输入的第二行包含 $$$m$$$ 整数($$$m$$$,而不是 $$$n$$$)$$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_i \le n$$$),其中 $$$x_i$$$ 是 $$$x$$$ 的第 $$$i$$$ 个元素。 $$$x$$$ 的元素可以重复并以任意顺序出现。
输出
打印 $$$n$$$ 整数:$$$f(p_1(n))、f(p_2(n))、\dots、f(p_n(n))$$$。
示例
输入 #1
4 4 1 2 3 4
输出 #1
3 4 6 5
输入 #2
5 5 2 1 5 3 5
输出 #2
9 8 12 6 8
输入 #3
2 10 1 2 1 1 2 2 2 2 2 2
输出 #3
3 3
注意
考虑第一个示例:
$$$x = [1, 2, 3, 4]$$$,所以
- 对于排列 $$$p_1(4) = [1, 2, 3, 4]$$$,答案是 $$$|1 - 2| + |2 - 3| + |3 - 4| = 3$$$;
- 对于排列 $$$p_2(4) = [2, 1, 3, 4]$$$,答案是 $$$|2 - 1| + |1 - 3| + |3 - 4| = 4$$$;
- 对于排列 $$$p_3(4) = [3, 1, 2, 4]$$$,答案是 $$$|2 - 3| + |3 - 1| + |1 - 4| = 6$$$;
- 对于排列 $$$p_4(4) = [4, 1, 2, 3]$$$,答案是 $$$|2 - 3| + |3 - 4| + |4 - 1| = 5$$$。
考虑第二个例子:
$$$x = [2, 1, 5, 3, 5]$$$,所以
- 对于排列 $$$p_1(5) = [1, 2, 3, 4, 5]$$$,答案是 $$$|2 - 1| + |1 - 5| + |5 - 3| + |3 - 5| = 9$$$;
- 对于排列 $$$p_2(5) = [2, 1, 3, 4, 5]$$$,答案是 $$$|1 - 2| + |2 - 5| + |5 - 3| + |3 - 5| = 8$$$;
- 对于排列 $$$p_3(5) = [3, 1, 2, 4, 5]$$$,答案是 $$$|3 - 2| + |2 - 5| + |5 - 1| + |1 - 5| = 12$$$;
- 对于排列 $$$p_4(5) = [4, 1, 2, 3, 5]$$$,答案是 $$$|3 - 2| + |2 - 5| + |5 - 4| + |4 - 5| = 6$$$;
- 对于排列 $$$p_5(5) = [5, 1, 2, 3, 4]$$$,答案是 $$$|3 - 2| + |2 - 1| + |1 - 4| + |4 - 1| = 8$$$。