思路1：枚举+二分

考虑任选一个区间 $[l, r]$ 删除，剩余的左部分是 $[1,l-1]$ ，右部分是 $[r+1,n]$

需要保证 $a[1,l-1]$ 是单调递增，$a[r+1,n]$ 也是单调递增的，且满足 $a[l-1]\leq a[r+1]$

枚举区间 $[l,r]$ 的左端点 $left$，，来二分出区间的右端点 $right$，check 函数是 $a[left-1]\leq a[right+1]$

我们需要保证 $a[1]\leq a[2]\leq \cdots\leq a[left-1]$ ，所以枚举左端点 $left$ ，直到 $a[left]<a[left-1]$ 停止。

题目描述

小红有一个长度为$n$的数组$a$，他想要使得数组$a$有序(单调不降），他必须选择一段区间$[l,r](1\le l,r\le n)$，将数组的这一段删除，其他的部分(如果存在的话)就按顺序拼在一起。 现在他想知道有多少种不同的选择区间的方案。

输入描述

第一行一个正整数$n(1≤n≤2\times 10^5)$，表示数组的长度。

第二行$n$个正整数$a_i(1≤a¡≤ 10^9)$，表示数组$a$。

输出描述

输出一行一个正整数表示答案。

样例

输入

3
1 2 3

输出

6

说明

可以选择:
[1, 1], [2, 2], [3, 3], [1, 2], [2, 3], [1, 3]
这六个区间