题目描述

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

名词解释

不动点

定义整数 i (1 ≤ i ≤ m) 是长度为 m 的数组 {$a_1$, $a_2$, ..., $a_m$}的一个不动点，当且仅当满足：

• $a_i = i$

排列

长度为 n 的排列是由 1,2,...,n 这 n 个整数按任意顺序组成的数组（每个整数均恰好出现一次）。
例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

子数组

从原数组中，连续地选择一段元素（可以全选，可以不选）得到的新数组。

输入格式

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

输出格式

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

4
1 4 2 3

8

2
2 1

3