小苯有一个长度为 的数组 ,他想要使得数组 有序(单调不降)。 为此,他必须选择一段区间 ,将数组的这一段删除,其他的部分(如果存在的话)就按顺序拼在一起。 现在他想知道有多少种不同的选择区间的方案。 注:小苯认为,空数组也满足有序,即你可以选择 这个区间。
输入描述:
输入包含两行。第一行一个正整数 ,表示数组的长度。第二行 个正整数 ,表示数组 。


输出描述:
输出一行一个正整数表示答案。
示例1

输入

3
1 2 3

输出

6

说明

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

输入

5
1 3 2 2 5

输出

10
加载中...