Остання битва
Близиться вирішальний бій між марсіанами та людьми. Шпигуни людей дізналися, що у марсіан залишилося 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