配点 : $200$ 点

問題文

$N$ 個の台が一列に並んでおり、左から $i$ 番目の台の高さは $H_i$ です。

高橋君は最初、左端の台の上に立っています。

高橋君は高い所が好きなので、次のルールで可能な限り移動を繰り返します。

• いま立っているのが右端の台ではなく、かつ、右隣にある台の高さが自分がいま立っている台より高いとき、右隣の台に移動する

最終的に高橋君が立っている台の高さを求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq H_i \leq 10^9$
• 入力に含まれる値は全て整数である

入力

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

$N$

$H_1$ $\ldots$ $H_N$

出力

答えを出力せよ。

5
1 5 10 4 2

10

最初、高橋君は左端にある高さ $1$ の台に立っています。右隣の台の高さは $5$ であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から $2$ 番目にある高さ $5$ の台に立っています。右隣の台の高さは $10$ であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から $3$ 番目にある高さ $10$ の台に立っています。右隣の台の高さは $4$ であり、いま立っている台より低いので、高橋君は移動をやめます。

よって、最終的に高橋君が立っている台の高さは $10$ です。

3
100 1000 100000

100000

4
27 1828 1828 9242

1828