Problem Description

You are given a sequence of $ N $ numbers. Let's call the $ i $-th number $ a_i $.

Find the number of pairs $ (l, r) $ such that $ a_l, a_{l+1}, ..., a_r $ is monotonically increasing, i.e., $l \leq r$ and $ a_i < a_{i+1} $ holds for all $ i $ satisfying $l \leq i < r$.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the number of pairs $ (l, r) $ such that $ a_l, a_{l+1}, ..., a_r $ is monotonically increasing in a single line.

Sample Input and Output

Sample Input #1

5
1 2 3 2 1

Sample Output #1

8

Sample Input #2

4
1 2 3 4

Sample Output #2

10

Sample Input #3

6
3 3 4 1 2 2

Sample Output #3

8

Sample Input #4

6
1 5 2 3 4 2

Sample Output #4

10

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq a_i \leq 10^5$
• All $ a_i $ are integers.

Partial Points

• If you correctly solve all test cases where $N \leq 3,000$, you will be awarded 40 points as partial credit.

Sample Explanation 1

The pairs $ (l, r) $ that satisfy the condition are $ (1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (4,4), (5,5) $, totaling 8 pairs.

Sample Explanation 2

All pairs $ (l, r) $ satisfying $1 \leq l \leq r \leq N$ meet the condition.

Sample Explanation 3

Note that, for example, $ 3, 3, 4 $ is not considered monotonically increasing in this problem.

见题面 Input 部分

见题面 Output 部分