Бартек — танымал техно-музыка продюсері және ол қазір өзінің келесі хитін жетілдіріп жатыр. Ол $1$-ден $n$-ге дейін ретімен нөмірленген $n$ ырғақтан (биттен) тұратын трек жасады. Музыка өңдеу бағдарламасында бірнеше сағат отырғаннан кейін, ол mp3 файлын экспорттамақшы болған кезде ырғақтардың қазіргі уақытта $a_1, a_2, \dots, a_n$ ретімен орналасқанын байқады. Бартекке ырғақтардың өсу ретін, яғни $1, 2, \dots, n$ ретін алу керек.

Бағдарлама екі түрлі амалды орындауға мүмкіндік береді:

• Соңғы ырғақты кез келген орынға жылжыту, мысалы $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Кез келген ырғақты басына жылжыту, мысалы $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Ырғақтарды өсу ретімен орналастыру үшін кемінде қанша амал қажет?

Кіріс деректер

Бірінші жолда ырғақтар санын білдіретін бүтін сан $n$ ($1 \le n \le 200\,000$) берілген.

Екінші жолда бағдарламадағы ырғақтардың ағымдағы ретін білдіретін, жұп-жұбымен әртүрлі $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$) берілген.

Шығыс деректер

Бір бүтін санды — қажетті ең аз амалдар санын шығарыңыз.

Мысалдар

Кіріс деректер 1

6
3 2 5 4 1 6

Шығыс деректер 1

4

Кіріс деректер 2

9
3 1 2 5 6 4 9 7 8

Шығыс деректер 2

6

Ескертпе

Біз $(3, 2, 5, 4, 1, 6)$ ырғақтар тізбегінен бастаймыз. Төрт амалмен қажетті ретке қол жеткізудің бір жолы:

• Соңғы ырғақты солға қарай екі орынға жылжыту: $(3, 2, 5, \underline{6}, 4, 1)$.
• $2$-ші ырғақты басына жылжыту: $(\underline{2}, 3, 5, 6, 4, 1)$.
• $1$-ші ырғақты басына жылжыту: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Соңғы ырғақты солға қарай екі орынға жылжыту: $(1, 2, 3, \underline{4}, 5, 6)$.

Төрт амалды қолданып басқа жолдармен де өсу ретін алуға болады, бірақ оны үш амалмен орындау мүмкін емес, сондықтан нәтиже — $4$.