問題文

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

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

---

制約

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

部分点

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

---

入力

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

$N$ $a_1$ $a_2$ … $a_N$

出力

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

---

入力例1

5
1 2 3 2 1

出力例1

8

条件を満たす$(l,r)$は$(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5)$の$8$つです。

---

入力例2

4
1 2 3 4

出力例2

10

$1≦l≦r≦N$を満たす$(l,r)$全てが条件を満たします。

---

入力例3

6
3 3 4 1 2 2

出力例3

8

例えば、$3, 3, 4$はこの問題で単調増加ではないことに注意してください。

---

入力例4

6
1 5 2 3 4 2

出力例4

10

---