Re: Вопросы для собеседования.
Добавлено: Пт май 05, 2017 1:31 am
В копилочку, от дяди Саши.
Как-то раз Twilight Sparkle захотела отсортировать последовательность целых чисел a1, a2, ..., an в не убывающем порядке. Будучи молодым единорогом, Twilight Sparkle умеет выполнять лишь одно действие — единичный сдвиг. Другими словами, она может переместить последний элемент последовательности в начало:
a1, a2, ..., an → an, a1, a2, ..., an - 1.
Какое минимальное количество действий понадобится Twilight Sparkle, чтобы отсортировать последовательность по неубыванию?
Входные данные
Первая строка содержит целое число n (2 ≤ n ≤ 105). Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105).
Выходные данные
Если последовательность невозможно отсортировать по неубыванию с помощью описанной операции, выведите -1. Иначе, выведите минимальное количество действий, необходимое для сортировки последовательности.