Определим \(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\) целых чисел: \(f(p_1(n)), f(p_2(n)), \dots, f(p_n(n))\).
Примечание
Рассмотрим первый тестовый пример:
\(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\).