Остання битва#8265

Остання битва

1 секунда

64 мегабайти

Легка

Близиться вирішальний бій між марсіанами та людьми. Шпигуну людей дізналися, що у марсіан залишилося $n$ бійців. Також відомо, що у людей, як і у марсіан, залишилося рівно $n$ бійців.

З досвіду минулих битв люди знають, що $i$ -го бійця може перемогти лише марсіанин з номером $i$ .

Командир вирішив вишикувати людей у шеренгу. Дізнавшись про плани марсіан, командир з'ясував, що боєць з $i$ -ї позиції в шерензі буде битися з марсіанином номер $a_{i}$ a_i. Люди переможуть, лише якщо кожен з бійців гарантовано виграє свій бій.

Спочатку командир поставив $i$ -го бійця на $i$ -у позицію в шерензі. Після цього він зрозумів, що у нього залишилося мало часу до битви, і люди можуть програти, якщо залишити все як є. За одну секунду він може переставити бійця з останнього місця на початок шеренги; після цієї операції він опиняється на першій позиції, а номер позиції кожного з інших бійців збільшується на $1$ .

Допоможіть командиру зрозуміти, за який мінімальний час він зможе перебудувати шеренгу так, щоб люди перемогли у вирішальному бою.

Вхідні дані

У першому рядку задано ціле число $n$ — кількість бійців у кожної зі сторін $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5).

У другому рядку задано $n$ різних цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n, де $a_{i}$ a_i — номер марсіанина, з яким буде битися боєць на $i$ -й позиції в шерензі ( $1 \leq a_{i} \leq n$ 1 \le a_i \le n, якщо $i \neq = j$ i \ne j, то $a_{i} \neq = a_{j}$ a_i \ne a_j).

Вихідні дані

Виведіть єдине число $k$ — мінімальне число секунд, за яке командир зможе перебудувати шеренгу так, щоб люди перемогли. Якщо перемогти марсіан неможливо, виведіть число «-1».

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі спочатку бійці стоять один навпроти одного наступним чином:

Марсіани: $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$