/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のディスコ社内ツアーの案内人です。
社内ツアーにおいて案内する部屋が N 箇所あり、それぞれの部屋には 1 から N の番号が割り振られています。建物の構造は環状となっており、 i(1≦i≦N-1) 番目の部屋から i+1 番目の部屋へと移動可能です。 N 番目の部屋からは 1番目の部屋へと移動可能です。これらの道は一方通行であり、逆向きに移動することはできません。
i 番目の部屋にいるとき、その部屋を見学するか隣の部屋へ移動するかどちらかを選ぶことが可能です。ただし、参加者に何度も同じ部屋を見学させると飽きてしまうため、見学はそれぞれの部屋につき 1 度しか行うことはできません。 あなたは社内ツアーを長年行ってきた経験から i番目の部屋を見学したときに得られる面白さはある整数 A_i で表されることを知っています。
社内ツアーは 1 番目の部屋から出発して、全ての部屋を見学し終わった状態で 1 番目の部屋にいるように終わらなくてはなりません。 あなたは参加者に社内ツアーを楽しんでもらうため、見学した部屋の面白さを見学した順番に並べたとき、広義単調増加列であるように部屋を案内することにしました。 このような制約のもとで社内ツアーを行うとき、建物内を最低何周する必要があるでしょうか？
ここで、 n 項からなる数列 a が a_1 ≦ a_2 ≦ ... ≦ a_n を満たすとき、 a は広義単調増加列であると呼ばれます。 また、 1 番目の部屋から移動し、全ての部屋を 1 度ずつ訪れて 1 番目の部屋に戻ってくることを、建物を 1 周すると呼びます。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 … A_N
- 1 行目に案内する部屋の数 N (2≦N≦10^{5}) が与えられる。
- 2 行目に各部屋の見学したときの面白さを表す整数 A_i (1≦A_i≦10^{5}) が空白区切りで与えられる。
出力
与えられた条件を満たすよう社内ツアーを行うのに必要な周回の回数の最低値を 1 行に出力せよ。末尾の改行を忘れないこと。
部分点
この問題には部分点が設定されている。
- 2≦N≦100 を満たすデータセットに正解した場合 20 点が与えられる。
- 1≦A_i≦Nかつi≠jにおいてA_i≠A_jが成立するようなデータセットに正解した場合上記の部分点とは別に 10 点が与えられる。
- 追加制約のないデータセットに正解した場合さらに 70 点が得られる。
入力例 1
5 1 4 3 2 5
出力例 1
3
- 下記のような順序で見学を行うことにより、 3 周で社内ツアーを終えることが可能です。 1 番目の部屋から出発し、すぐに 1 番目の部屋を見学することは許されています。ツアーは全ての部屋を見学し終えた状態で 1 番の部屋にいる状態で終わらなくてはならないことに注意してください。
- 1 周目において、 1 番目の部屋と 4 番目の部屋を見学する。
- 2 周目において、 3 番目の部屋を見学する。
- 3 周目において、 2 番目の部屋と 5 番目の部屋を見学する。
- このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。
入力例 2
5 1 2 3 4 5
出力例 2
1
- 1 周目において、全ての部屋を見学することが可能です。
- このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。
入力例 3
5 5 1 2 3 4
出力例 3
1
- 最後に 1 番目の部屋を見学した直後にツアーを終了することで 1 周でツアーを終了することが可能です。
- このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。
入力例 4
8 1 1 1 2 2 2 3 3
出力例 4
1
- 部屋の面白さは重複しているものもあることに注意してください。
- このケースは上記の部分点の 1 つ目の条件を満たしますが 2 つ目の条件は満たしません。