Counting Consecutive Ascending Subarrays

Interview

Time limit1sMemory limit1024 MB

Summary

Given a permutation A of length N, count the pairs (i, j) with i at most j where A_i through A_j are strictly increasing.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

You are given a sequence $A_1, \cdots, A_N$ of length $N$ . Every number in the sequence is a distinct integer from $1$ to $N$ . Count the pairs of integers $(i, j)$ that satisfy all of the following conditions.

$1 \le i \le j \le N$ .
From the $i$ -th number to the $j$ -th number of $A$ , the sequence is in ascending order. That is, for every integer $k$ with $i \le k < j$ , $A_k < A_{k+1}$ .

Input

The first line contains the length $N$ of the sequence. $(1 \le N \le 200\,000)$

The next line contains the elements $A_1, A_2, \cdots, A_N$ separated by spaces. $(1 \le A_i \le N$ ; $A_1, A_2, \cdots, A_N$ are distinct integers. $)$

Output

Print the number of pairs $(i, j)$ that satisfy the conditions.

Examples1

Example 1
Input
```
5
1 2 5 4 3
```
Expected output
```
8
```