Problem Statement

$N$個の数からなる数列が与えられます。$i$番目の数を$a_i$と呼びましょう。

$a_l,a_{l+1},...,a_r$ が単調増加、すなわち $l≦r$ であって $a_i<a_{i+1}$ が$l≦i<r$ を満たす全ての$i$に対して成り立つような$(l,r)$の数を求めてください。

Constraints

• $1≦N≦10^5$
• $1≦a_i≦10^5$
• $a_i$は全て整数である

部分点

• $N ≦ 3,000$ を満たすテストケース全てに正解した場合、部分点として$40$点が与えられる。

Input

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

N
a_1 a_2 … a_N

Output

$a_l,a_{l+1},...,a_r$ が単調増加となるような$(l,r)$の数を $1$ 行に出力せよ。