#WD231105A. 自福串(string)--自编题

#WD231105A. 自福串(string)

题目背景

（啊哦！题目背景不见了，去其他地方找找看吧~）

题目描述

前提：$Zi\ Fu\ Chuan\ (ZFC)$是它，不是他/她

• 一个 自福串 由 数字 构成，$a_i$ 表示该自福串的第 $i$ 位。

• 一个 自福串 的子串 $A_{l,r}$ 表示由 $a_{l},a_{l+1},…,a_r$ 依次拼接而成的自福串

给定一个自福串 ，设：

1. $f(A_{l,r})=max_{i=l}^{r}a_i$ .
2. $g(A_{l,r})=a_{1}\left|a_{2}\right| \ldots \mid a_{n}$ .

现在 $\mathrm{ZFC}$ 想要问你, 对于给定的自福串 $S$, 有多少个子串 $A_{l,r}$, 满足 $g(A_{l,r})>f(A_{l,r})$ 。

输入格式

第一行一个整数 $n$ 。

接下来一行 $n$ 个整数, 第 $i$ 个数表示 $S_{i}$ 。

输出格式

输出一个数, 表示满足条件的子串的个数。

样例

输入数据 1

5 
3 2 1 6 5

输出数据 1

8

输入数据 2

4 
3 3 3 3

输出数据 2

0

更多样例，见选手文件。

样例解释

这是一道原题，细心的童鞋们已经发现了，而本题作者加强数据后，成功的卡死了自己的 $100pts$ 骗分代码。

数据规模与约定

对于 $20 %$ 的数据, $n \leq 300$ 。

对于 $50 %$ 的数据, $n \leq 3000$ 。

对于 $80 %$ 的数据, $n \leq 10^{5}$ 。

对于 $100 %$ 的数据, $n \leq 10^{6}, a_{i} \leq 10^{9}$ 。