Сіз мәліметтер мұрағатында жұмыс жасайсыз, онда сандық тізбектер сақталады. Кейбір тізбектер өздерінің реттелуін жоғалтқан, және сіз оларды қалпына келтіруіңіз керек.

Алайда, жүйе сандардың мәндерін өзгертуге мүмкіндік береді, бірақ олардың орындарын ауыстыруға болмайды.

Сіздің мақсатыңыз — тізбекті келесі шарттардың біріне сай ету үшін қажетті ең аз ауыстыру санын табу:

• Өсу бойынша (әрбір келесі сан \(\geq\) алдыңғысынан кіші емес).

• Кемуі бойынша (әрбір келесі сан \(\leq\) алдыңғысынан үлкен емес).

Бұл ең аз өзгертулер санымен жасалуы керек.

Енгізу

Бірінші жолда \(n\) саны беріледі — массивтің ұзындығы \((1\leq n\leq 10^5)\). Екінші жолда \(n\) саннан тұратын тізбек \(a_1, a_2, ..., a_n\) — массивтің өзі \((-10^9\leq a_i \leq 10^9)\).

Шығару

Бір бүтін санды шығарыңыз — массивті өспелі немесе кемімелі ету үшін ең аз ауыстырулар саны.

Мысалдар

Енгізу 1

5
4 2 5 7 8

Жауап 1

1

Енгізу 2

4
10 9 8 7

Жауап 2

0

Енгізу 3

6
1 3 2 4 6 5

Жауап 3

2

Ескертпелер

Бірінші мысалдың түсіндірмесі:

Егер екінші санды \(2 \rightarrow 4\) ауыстырсақ, біз өспелі қатар аламыз: \([4,4,5,7,8]\)

Ең аз ауыстырулар саны \(= 1\).

Екінші мысалдың түсіндірмесі:

Тізбек қазірдің өзінде кемімелі, сондықтан ешқандай өзгеріс қажет емес.