0292 - たのしい家庭菜園 (Growing Vegetables is Fun)

問題

　家庭菜園が趣味の JOI 君は，毎年，自分の畑で IOI 草という植物を育てている．JOI 君の畑は東西方向に並んだ N 個の区画に分かれており，西側から順に 1 から N まで番号が付いている．IOI 草は全部で N 株あり，それぞれの区画に 1 株ずつ植えてある．区画 i に植えられている IOI 草は，春になると背丈 hi まで伸び，その後は伸びない．
　春になって様子を見に行った JOI 君は，IOI 草の配置が予定とは異なる配置になっていることに気づいた．IOI 草は日光を多く必要とする植物で，ある区画に植えられている IOI 草について，その区画より番号の小さい区画と番号の大きい区画の両方にその IOI 草より背丈の高い IOI 草があると，その IOI 草は夏になる前に枯れてしまう．すなわち，どの IOI 草も枯れないようにするためには，以下の条件が満たされなければならない．

• 2 ≤ i ≤ N - 1 を満たすどの整数 i についても，以下の 2 つの条件のうち少なくとも 1 つが成立する．
• 1 ≤ j ≤ i - 1 を満たすすべての整数 j について，h_j ≤ h_i を満たす．
• i + 1 ≤ k ≤ N を満たすすべての整数 k について，h_k ≤ h_i を満たす．

　IOI 草は大変高価なため，どの IOI 草も枯れないように JOI 君は IOI 草の並べ替えを行うことにした．IOI 草は大変大きく，かつ繊細な植物なため，JOI 君は隣り合う 2 つの IOI 草を並べ替えることしかできない．つまり，1 回の操作で JOI 君は区画 i (1 ≤ i ≤ N - 1) を任意に 1 つ選び，区画 i の IOI 草と区画 i + 1 の IOI 草を入れ替えることができる．夏が近づくにつれて枯れる可能性が高くなるので，すべての IOI 草が枯れないようにするために必要な操作回数の最小値が知りたい．

課題

　JOI 君の畑の区画数と，それぞれの IOI 草の背丈の情報が与えられたとき，すべての IOI 草が枯れないように並べ替えるために必要な操作回数の最小値を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれている．N は JOI 君の畑の区画数を表す．
• 続く N 行には，IOI 草の背丈に関する情報が書かれている．これらの行のうち i 行目 (1 ≤ i ≤ N) には整数 D_i が書かれている．D_i は区画 i に植えられている IOI 草の春になった時点での背丈を表す．

出力

　標準出力に，必要な操作回数の最小値を表す整数を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

• 3 ≤ N ≤ 300 000．
• 1 ≤ D_i ≤ 1 000 000 000．

小課題

小課題 1 [10 点]

• N ≤ 8 を満たす．

小課題 2 [20 点]

• N ≤ 20 を満たす．

小課題 3 [15 点]

• N ≤ 5 000 を満たす．

小課題 4 [55 点]

　追加の制限はない．

入出力例

入力例 1

6
2
8
4
5
3
6

出力例 1

3

　初期状態で IOI 草は下図のような配置となっている．

　例えば，次のように動かすと，3 回の操作で IOI 草が枯れない配置にすることができる．

1. 区画 2 と区画 3 の IOI 草を入れ替える．	2. 区画 3 と区画 4 の IOI 草を入れ替える．

3. 区画 5 と区画 6 の IOI 草を入れ替える．	4. この配置は，IOI 草が枯れない配置である．

入力例 2

5
4
4
2
4
4

出力例 2

2

　区画 3 にある IOI 草を区画 1 または区画 5 に動かせば良い．

入力例 3

4
1
3
4
2

出力例 3

0

　この入力例において，IOI 草を入れ替える操作をする必要はない．