問題文

11 段の本棚に NN 冊の本が収納されています。
本にはそれぞれ番号がついており、左から ii 番目の本の番号は AiA_i です。

あなたは、この本棚に対して以下の操作を N1N - 1 回まで行うことができます。

  • ii 回目の操作では、1jNi+11 \leq j \leq N - i + 1 をみたす整数 jj を選び、左から jj 番目の本を取り出す。

本棚に収納されている本が番号について昇順に並んでいるために必要な操作回数の最小値を求めてください。

制約

  • 1N1051 \leq N \leq 10^5
  • 1Ai1091 \leq A_i \leq 10^9
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1A2A_2   . . .   ANA_N

出力

問題の答えを一行に出力せよ。

入出力例

入力例1
4
1 4 3 2
出力例1
2

例えば、次の 22 回の操作を行うことによって条件を満たすことができます。

  • 左から 33 番目の本を取り出す。 本棚に収納されている本は (1,4,2)(1, 4, 2) となる。
  • 左から 22 番目の本を取り出す。 本棚に収納されている本は (1,2)(1, 2) となる。
入力例2
6
1 1 10 10 100 100
出力例2
0

既に条件を満たしているため、操作を行う必要はありません。

Submit


Go (1.21)