### 问题描述 小辉拥有一个长度为 $n$ 的数组 $A$。他认为一个区间是**好的区间**，如果该区间从 $l$ 到 $r$ （其中 $l \leq r$）满足以下特性： - 任选区间 $l$ 到 $k$（其中 $l \leq k \leq r$）作为数组 $A$ 的子集 $B$。 - 对于所有这样的 $B$，设 $mx$ 是 $B$ 的最大值。那么，要使 $l, r$ 成为**好的区间**，$mx$ 必须满足以下其中一个条件： 1. $mx = 1$。 1. 当 $mx > 1$ 时，对于任意 $j$ （其中 $1 < j \leq mx$），$B$ 中小于 $j$ 的数的数量要大于或等于 $j$ 的数量。 最后，小辉想计算数组 $A$ 中有多少个这样的**好的区间**。 ### 输入格式 第一行一个数 $n$ 。 第二行 $n$ 个数，第 $i$ 个数表示 $A_i$ 。 ### 输出格式 输出一个整数，表示数组 $A$ 中**好的区间**的个数。 ### 样例一输入 ```text 6 1 2 1 2 1 3 ``` ### 样例一输出 ```text 11 ``` ### 样例二输入 ```text 6 1 1 2 2 3 3 ``` ### 样例二输出 ```text 8 ``` ### 说明 样例一中，区间 $[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,3],[3,4],[3,5],[3,6],[5,5]$ 都是**好的区间**，所以答案为 $11$ 。 样例二中，区间 $[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,2],[2,3]$ 都是**好的区间**，所以答案为 $8$ 。 ### 评测数据规模 对于 $100$% 的评测数据， $1\leq n \leq 10^6,1\leq A_i\leq n$ 。