17730번 - 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．