시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

家庭菜園が趣味の 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 について,hj ≤ hi を満たす.
    • i + 1 ≤ k ≤ N を満たすすべての整数 k について,hk ≤ hi を満たす.

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) に は整数 Di が書かれている.Di は区画 i に植えられている IOI 草の春になった時点での背丈を表す.

출력

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

제한

  • 3 ≤ N ≤ 300 000.
  • 1 ≤ Di ≤ 1 000 000 000.

예제 입력 1

6
2
8
4
5
3
6

예제 출력 1

3

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

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

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

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

区画 5 と区画 6 の IOI 草を入れ替える.

この配置は,IOI 草が枯れない配置である.

예제 입력 2

5
4
4
2
4
4

예제 출력 2

2

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

예제 입력 3

4
1
3
4
2

예제 출력 3

0

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