E. Специальные перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим $$$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$$$. Эта функция означает сумму дистанций между соседними элементами $$$x$$$ в $$$p$$$.

Ваша задача — посчитать $$$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$$$ равно $$$i$$$-му элементу $$$x$$$. Элементы $$$x$$$ могут повторяться и идти в случайном порядке.

Выходные данные

Выведите $$$n$$$ целых чисел: $$$f(p_1(n)), f(p_2(n)), \dots, f(p_n(n))$$$.

Примеры
Входные данные
4 4
1 2 3 4
Выходные данные
3 4 6 5
Входные данные
5 5
2 1 5 3 5
Выходные данные
9 8 12 6 8
Входные данные
2 10
1 2 1 1 2 2 2 2 2 2
Выходные данные
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]$$$, so

  • для перестановки $$$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$$$.