题目描述

小明定义一个数组的权值为：将其从小到大排序后，不动点的数量。 现在，小明拿到了一个长度为 $n$ 的排列，他想知道其所有子数组的权值之和。

名词解释

不动点：定义整数 $i\ (1 \le i \le m)$ 是长度为 $m$ 的数组 $\{a_1,a_2,\dots,a_m\}$ 的一个不动点，当且仅当满足 $a_i = i$。 排列：长度为 $n$ 的排列是由 $1,2,\dots,n$ 这 $n$ 个整数按任意顺序组成的数组（每个整数均恰好出现一次）。 例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，前者存在重复元素，后者包含超出范围的数。 子数组：从原数组中连续地选择一段元素（可全选、可选单个）得到的新数组。

输入格式

第一行输入一个整数 $n\ (1 \le n \le 300000)$，代表排列中的元素数量。 第二行输入 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n\ (1 \le a_i \le n)$，代表一个排列。

输出格式

输出一个整数，代表所有子数组的权值之和。

样例输入 1

4
1 4 2 3

样例输出 1

8

样例输入 2

2
2 1

样例输出 2

3