Дан массив целых чисел \(a_1, a_2, \ldots, a_n\). Вы можете выполнять два типа операций с этим массивом:
- Сдвиг: переместить последний элемент массива на первое место и сдвинуть все остальные элементы вправо, таким образом получится массив \(a_n, a_1, a_2, \ldots, a_{n-1}\).
- Разворот: перевернуть весь массив, таким образом получится массив \(a_n, a_{n-1}, \ldots, a_1\).
Ваша задача — отсортировать массив в порядке неубывания с использованием минимального количества операций или определить, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите число \(k\) — минимальное количество операций, необходимых для сортировки массива. Если невозможно отсортировать массив с помощью этих операций, выведите \(-1\).
Примечание
В первом наборе входных данных примера, чтобы отсортировать массив [\(3, 2, 1, 5, 4\)] нужно выполнить \(3\) операции:
- Сдвиг, чтобы получить массив [\(4, 3, 2, 1, 5\)];
- Сдвиг, чтобы получить массив [\(5, 4, 3, 2, 1\)];
- Разворот, чтобы получить массив [\(1, 2, 3, 4, 5\)].
В третьем наборе входных данных примера можно показать, что массив невозможно отсортировать с помощью данных операций.
В седьмом наборе входных данных примера, чтобы отсортировать массив [\(4, 1, 3, 4, 4\)] нужно выполнить \(3\) операции:
- Разворот, чтобы получить массив [\(4, 4, 3, 1, 4\)];
- Сдвиг, чтобы получить массив [\(4, 4, 4, 3, 1\)];
- Разворот, чтобы получить массив [\(1, 3, 4, 4, 4\)].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
5
3 2 1 5 4
5
1 1 2 1 1
4
3 7 10 5
5
1 2 3 4 5
2
5 1
3
3 4 1
5
4 1 3 4 4
3
5 1 1
4
2 5 5 4
5
2 2 1 1 2
2
5 5
|
3
2
-1
0
1
1
3
1
2
2
0
|