Subarray Removal

Given an integer array arr of length n, count the subarrays (contiguous segments, distinguished by position) whose removal leaves an array that is non-empty and sorted in non-decreasing order (adjacent elements may be equal).

输入格式

The first line contains an integer n; the second line contains n integers arr[0..n−1]. 1≤n≤200000, 1≤arr[i]≤10^9.

输出格式

Output one integer: the number of subarrays that satisfy the condition.

样例 1

输入：

4
1 2 1 2

输出：

7

样例 2

输入：

3
3 1 2

输出：

3

样例 3

输入：

6
1 2 2 6 1 3

输出：

10

样例说明

Example 1: arr=[1,2,1,2] has 10 subarrays. The 7 removals that leave [1,2], [2], [1,1,2], [1,2], [1], [1,2,2], and [1,2] satisfy the condition; removing [1] leaves [2,1,2] and removing the last [2] leaves [1,2,1], neither of which is sorted, and removing the whole array leaves an empty array, which also fails. Example 2: removing [3], [3,1], or [1,2] satisfies the condition, so the answer is 3. Example 3: the qualifying subarrays are [1,2,2,6], [1,2,2,6,1], [2,2,6], [2,2,6,1], [2,2,6,1,3], [2,6,1], [2,6,1,3], [6,1], [6,1,3], and [1,3], so the answer is 10.