| Codeforces Round 421 (Div. 1) |
|---|
| Закончено |
Недавно Мистер Б получил странный сигнал из космоса, который он непременно решил исследовать.
После некоторых преобразований сигнал оказался перестановкой p из n элементов, либо некоторым ее циклическим сдвигом. Для дальнейшего анализа Мистеру Б понадобилась некоторая определенность, а потому он захотел выбрать из всех циклических сдвигов данной перестановки некоторую с наименьшим отклонением.
Отклонением перестановки p назовем величину 
.
Найдите циклический сдвиг перестановки p с наименьшим отклонением. Если таких несколько, выведите номер любого из них.
Номером k (0 ≤ k < n) циклического сдвига перестановки p определим как число сдвигов вправо, необходимых для получения этого сдвига, то есть:
- k = 0: сдвиг p1, p2, ... pn,
- k = 1: сдвиг pn, p1, ... pn - 1,
- ...,
- k = n - 1: сдвиг p2, p3, ... pn, p1.
В первой строке задано одно натуральное число n (2 ≤ n ≤ 106) — размер перестановки.
В следующей строке задано n натуральных чисел p1, p2, ..., pn (1 ≤ pi ≤ n) через пробел — элементы перестановки. Гарантируется, что все элементы различны.
Выведите два целых числа через пробел: минимальное возможное отклонение циклического сдвига перестановки p и номер такого сдвига. Если таких сдвигов несколько, выведите номер любого из них.
3
1 2 3
0 0
3
2 3 1
0 1
3
3 2 1
2 1
В первом примере заданная перестановка p является тождественной, поэтому ее отклонение равно 0, а соответствующий номер сдвига равен 0.
Во втором примере отклонение перестановки p равно 4, отклонение 1-го циклического сдвига (1, 2, 3) равно 0, отклонение 2-го циклического сдвига (3, 1, 2) равно 4, оптимальным является 1-й циклический сдвиг.
В третьем примере отклонение перестановки p равно 4, отклонение 1-го циклического сдвига (1, 3, 2) равно 2, отклонение 2-го циклического сдвига (2, 1, 3) также равно 2, оптимальными являются 1-й и 2-й циклические сдвиги.
