我们定义一个有效序列为：该序列两端的数一个为最小值，另一个为次小值。（即序列两端以外的数一定大于等于最左边的数且大于等于最右边的数） 现在给你一个序列 a ，想让你找到它的连续子序列中有多少个有效序列(比如 ，1 2 ，2 3，1 2 3 是序列 1 2 3 的连续子序列，但是 1 3 不是) 注：长度为 2 的子序列，一定为有效序列，长度为 1 的子序列，一定不是有效序列
输入描述:
第一行输入一个整数 n 代表这个序列的长度接下来输入 n 个整数，a[i] 代表系列中第 i 个元素对于 20% 的数据, 1 ≤ n ≤ 100对于 70% 的数据, 1 ≤ n ≤ 3,000对于 100% 的数据, 1 ≤ n ≤ 100,000对于 100% 的数据, 1 ≤ a[i] ≤ 1,000,000,000


输出描述:
输出一个正整数表示有效序列的数量。
示例1

输入

4
1 3 1 2

输出

4

说明

一共有 4 组有效序列，分别为：
子序列[1,3] 因为长度为 2，一定为有效序列
子序列[1,3,1] 因为第2个数 “3” 大于第 1 个数和第 3 个数
子序列[3,1] 因为长度为 2，一定为有效序列
子序列[1,2] 因为长度为 2，一定为有效序列
示例2

输入

4
1 1 2 1

输出

5

说明

一共有6个长度不小于2的连续子序列，除了[1,1,2]以外，其他5个都是有效子序列
示例3

输入

7
1 4 2 5 7 1 3

输出

10

说明

一共有10组，分别为：
[1,4], [1,4,2], [1,4,2,5,7,1], [4,2], [2,5], [2,5,7,1], [5,7], [5,7,1], [7,1], [1,3]
加载中...