题目描述

图上有 $n$ 个点，编号为 $1,2,\cdots,n$，第 $i$ 个点上有一个权值 $a_i$，满足 $1 \leq a_i \leq n$。初始时，对于所有 $1 \leq i \leq n-1$，存在一条边 $(i,i+1)$。

定义 $f(l,r)$ 为只保留图上权值在 $[l,r]$ 内的所有点形成的连通块数量。你需要计算：

输入格式

第一行包含一个整数 $n$，表示图的顶点数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示每个顶点的权值。

输出格式

输出一个整数，表示答案。

4
2 1 1 3

11

数据范围

• 对于 $30\%$ 的数据，$n \le 100$；
• 对于 $60\%$ 的数据，$n \leq 5 \times 10^3$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5, 1\leq a_i \leq n$。