Story

♠

春休みだというのに、おうちでゴロゴロしています。外はまだ寒い。外に出ない理由はそれだけです。

あなたにはたくさんの友達がいます。
さっそく友達を招いて遊ぼうと思いましたが、あいにくそういう系のゲームがありません。そこであなたが探し出したものは、トランプでした。

トランプで何をして遊ぼうかな？

あなたはトランプゲームについて調べてみると、「たこやき」という遊び方がありました。
これをあなたの友達とやってみようと思っているようですが、せっかくなら戦略を考えて実践で圧倒的な強さを見せてしまいましょう。

ただし、ズルをして...ね？

問題

$N$ 枚のトランプがあります。そのうち $i\ (1\le i\le N)$ 枚目のトランプに書かれた数字は $A_i$ であり、裏向きに置いてあります。
ここでは $i$ 枚目のトランプを、トランプ $i$ と呼ぶことにします。

最初にあなたは好きなトランプを一つ選び、そのトランプを表向きにします。その後、次の操作を可能な限り繰り返し行います。

• 表向きにした結果書かれた数字が $x$ であったとき
  • まだトランプ $x$ が表向きになっていないなら、そのトランプを表向きにする。
  • 既にトランプ $x$ が表向きになっているなら、操作を終了する。

あなたは透視能力の持ち主なので、トランプに書かれた数字を事前に見ることができます。

最初に選ぶトランプを適切に決めた時、最大で何回の操作を行うことができますか？

入力

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

制約

• $1\le N\le 10^5$
• $A$ は $(1,2,\dots,N)$ を適切に並び替えて得られる

出力

答えを出力せよ。

入出力例

5
2 3 1 4 5

3

例えばトランプ $3$ を選ぶとします。

• $1$ 回目の操作で、トランプ $3$ を表向きにします。
• トランプ $3$ に書かれた数字は $1$ です。そのため $2$ 回目の操作でトランプ $1$ を表向きにします。
• トランプ $1$ に書かれた数字は $2$ です。そのため $3$ 回目の操作でトランプ $2$ をめくります。
• トランプ $2$ に書かれた数字は $3$ です。しかしトランプ $3$ は既に表向きになっているので、操作を終了します。

この場合 $3$ 回の操作をすることができ、これが最大となります。$4$ 回以上連続で操作をすることが可能なトランプの選び方は存在しません。

3
1 2 3

1

選んだトランプ自身でしか表向きにすることはできません。

10
10 4 3 6 2 7 9 8 1 5

8