eolymp
bolt
Try our new interface for solving problems
Məsələlər

Последняя битва

Последняя битва

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

По опыту прошлых сражений люди знают, что i-го человека может победить только один марсианин, который имеет номер i.

Командир решил выстроить людей в шеренгу. Узнав планы марсиан, командир выяснил, что человек с i-й позиции в шеренге будет сражаться с марсианином номер a[i]. Люди победят, только если каждый из бойцов гарантированно победит в своём бою.

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

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

Giriş verilənləri

В первой строке задано целое число 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] ).

Çıxış verilənləri

Выведите единственное число 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

Nümunə

Giriş verilənləri #1
5
1 4 2 3 5
Çıxış verilənləri #1
2
Giriş verilənləri #2
5
1 3 5 2 4
Çıxış verilənləri #2
-1
Mənbə XXV Командный чемпионат школьников Санкт-Петербурга по программированию Санкт-Петербург, Университет ИТМО, 5 ноября 2017 года