Последняя битва
Близится решающий бой между марсианами и людьми. Шпионы людей выяснили, что у марсиан осталось n бойцов. Также выяснилось, что у людей, как и у марсиан, осталось ровно n бойцов.
По опыту прошлых сражений люди знают, что i-го человека может победить только один марсианин, который имеет номер i.
Командир решил выстроить людей в шеренгу. Узнав планы марсиан, командир выяснил, что человек с i-й позиции в шеренге будет сражаться с марсианином номер a[i]. Люди победят, только если каждый из бойцов гарантированно победит в своём бою.
Сначала командир поставил i-го человека на i-ю позицию в шеренге. После этого он понял, что у него осталось мало времени до битвы и люди могут проиграть, если оставить все как есть. За одну секунду он может переставить человека с последнего места в начало шеренги, после этой операции он оказывается на первой позиции, а номер позиции каждого из остальных бойцов увеличивается на 1.
Помогите командиру понять, за какое минимальное время он сможет перестроить шеренгу так, чтобы люди победили в решающем бою.
Входные данные
В первой строке задано целое число n — количество бойцов у каждой из сторон (1 ≤ n ≤ 2 * 10^5).
Во второй строке задано n различных целых чисел a[1]; a[2]; ...; a[n], где a[i] — номер марсианина, с которым будет сражаться человек на i-й позиции в шеренге (1 ≤ a[i] ≤ n, если i ̸= j, то a[i] ̸= a[j] ).
Выходные данные
Выведите единственное число k — минимальное число секунд, за которое командир сможет перестроить шеренгу так, чтобы люди победили. Если победить марсиан невозможно, выведите число «-1».
####Замечание
В первом примере исходно бойцы стоят друг напротив друга следующим образом:
Марсиане: 1 4 2 3 5
Люди: 1 2 3 4 5
Люди проигрывают, поскольку марсиане номер 1 и 5 выигрывают свои поединки. После первой перестановки расстановка бойцов становится такой:
Марсиане: 1 4 2 3 5
Люди: 5 1 2 3 4
Теперь марсиане 2 и 3 выигрывают свой бой, поэтому необходимо провести ещё перестановку. После неё расстановка бойцов становится такой, что все люди выигрывают свой бой.
Марсиане: 1 4 2 3 5
Люди: 4 5 1 2 3