题解

题面描述

给定一个长度为$n$的整数数组$[a_1,a_2,\dots,a_n]$，我们称一个数组是“好数组”，当且仅当将该数组的一个后缀整体移动到最前面后，该数组变成非降序。举例：

• $[3,7,7,9,2,3]$ 是好数组，因为可以将后缀 $[2,3]$ 移到前面，得到 $[2,3,3,7,7,9]$，这是非降序的。
• $[1,2,3,4,5]$ 是好数组，因为可以将整个数组（后缀长度为$n$）移动至前面后保持不变，仍然是非降序的。
• $[5,2,2,1]$ 不是好数组，任意后缀移动后都无法得到非降序数组。

题目内容

游游定义一个数组是“好数组",当仅当将该数组的一个后缀整体移动到最前面后，该数组变成非降序。 例如：

$[3,7,7,9,2,3]$ 是好数组，因为可以将 $[2,3]$ 移动到前面，数组变成 $[2,3,3,7,7,9]$ 。

$[1,2,3,4,5]$ 是好数组，因为可以将 $[1,2.3,4,5]$ 移动到最前面，该数组不变，依然非降序。

$[5,2,2,1]$ 不是好数组。

现在给定一个数组，游游希望你求出有多少非空连续子数组是好数组。

连续子数组为从原数组中，连续的选择一段元素(可以全选)得到的新数组。

输入描述

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表游游拿到的数组。

$1≤n≤10^5$

$1≤a_i≤10^9$

输出描述

一个正整数，代表连续好子数组的数量。

样例1

输入

3
3 2 1

输出

5

说明

$3$ 个大小为 $1$ 的和 $2$ 个大小为 $2$ 的连续子数组均为好数组。

大小为 $3$ 的 $[3,2,1]$ 不是好数组。所以共有 $5$ 个连续好子数组。