对于一个长度为 $N$ 的序列 $A$ 以及 $1 \le i \le j \le N$，令 $f(i, j)$ 表示将序列 $A$ 中从第 $i$ 个元素到第 $j$ 个元素的连续子序列翻转后得到的序列。例如，如果 $A = [3, 1, 4, 1, 5]$，那么 $f(2, 3) = [3, 4, 1, 1, 5]$，$f(1, 5) = [5, 1, 4, 1, 3]$，且 $f(1, 1) = [3, 1, 4, 1, 5]$。

对于 $f(i, j)$，共有 $\frac{N(N+1)}{2}$ 种不同的选择 $i$ 和 $j$ 的方式。给定序列 $A$，求在所有可能的 $f(i, j)$ 中，本质不同的序列个数。

输入格式

第一行包含一个整数 $N$，表示序列 $A$ 的长度。($1 \le N \le 500\,000$)

第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$，表示序列 $A$ 的元素。($1 \le A_i \le 10^9$)

输出格式

输出一行，包含一个整数，表示所有可能的 $f(i, j)$ 中本质不同的序列个数。

样例

输入样例 1

4
3 1 4 1

输出样例 1

6

输入样例 2

1
20250726

输出样例 2

1

说明

在第一个样例中，以下是所有可能的 $f(i, j)$ 序列：

• $f(1, 1) = f(2, 2) = f(2, 4) = f(3, 3) = f(4, 4) = [3, 1, 4, 1]$
• $f(1, 2) = [1, 3, 4, 1]$
• $f(1, 3) = [4, 1, 3, 1]$
• $f(1, 4) = [1, 4, 1, 3]$
• $f(2, 3) = [3, 4, 1, 1]$
• $f(3, 4) = [3, 1, 1, 4]$