問題
Kambaくんは法則性のある数列がとても大好きです。最近は大きい順、小さい順に並んでいる数列だけでは満足できなくなってしまいました。そこでKambaくんは小さい順と大きい順を組み合わせたハイブリットである山形がとても気持ちよく感じることができると気がつきました。
長さ$N$の整数列が与えられるため、その数列がKambaくんが好きなものなら$1$、好きではないのなら$0$を出力してください。Kambaくんのすきな山形は長さ$n$の整数列$a = (a_1, a_2, \dots, a_n)$において、最大の値の場所を$m$とするとき、以下の２つの条件を満たす時である。
- $a_l \leq a_{l+1} \leq \cdots \leq a_m$ かつ $a_l < a_m$を満たす組み合わせが存在する $(1 \leq l < m)$
- $a_m \geq a_{r} \geq \cdots \geq a_N$ かつ $a_m > a_r$を満たす組み合わせが存在する $(m < r \leq N)$
●GOOD
$1,2,3,4,3,2,1$
$1,2,2,3,4,4,3,2,2$
$1,1,2,2,1,1$
$1,2,3,3,4,5,5,4,2,1$
●BAD
$5,5,5,5$
$5,5,5,4,3$
$1,2,3,4$
$5,4,3,2,3$
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1\:\:A_2\:\:A_3 … A_N$
1行目に整数$N$が与えられる。 2行目に整数$A_i (1 \leq i \leq N)$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $3 \leq N \leq 10^{6}$
- $0 \leq A_i \leq 10^9 (1 \leq i \leq N)$
入出力例
入力例1
5
1 5 4 3 1
出力例1
1
これが山形です！
入力例2
8
1 8 3 4 7 2 3 8
出力例2
0
なんてバラバラな数列なのでしょう。
入力例3
3
1 2 3
出力例3
0
これではただの坂です。