问题文

给定一个由N个数字组成的数列。我们将第i个数字称为$a_i$。

求满足条件$a_l,a_{l+1},...,a_r$ 在$l≦r$且对于所有满足$l≦i<r$的$i$都有$a_i<a_{i+1}$的$(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

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

满足条件的$(l,r)$是所有满足$1≦l≦r≦N$的组合。

---

输入例3

6
3 3 4 1 2 2

输出例3

8

请注意，$3, 3, 4$不满足升序条件。

---

输入例4

6
1 5 2 3 4 2

输出例4

10

---