题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_{n}$，其中每个元素不小于 $1$、不大于 $n$，且 $1$ 到 $n$ 中每个数字最多出现两次。

称两个可重集合 $S,T$ 相同当且仅当对于任意 $x \in S \cup T$ ，其在 $S$ 和 $T$ 中出现次数相同；反之，两个可重集合 $S,T$ 不同当且仅当存在 $x \in S \cup T$，其在 $S$ 和 $T$ 中出现次数不同。

称可重集合 $S \subseteq \{1, 1, 2, 2, \cdots, n, n\}$ 合法当且仅当存在一个区间 $[l, r]\ (1\leq l \leq r \leq n)$，使得可重集合 $T = \{a_l, a_{l+1}, \cdots, a_r\}$ 和 $S$ 相同。

你需要求出存在多少个不同的合法可重集合。

输入格式

从标准输入读入数据。

第一行包含一个正整数 $n$，表示序列长度。

第二行包含 $n$ 个由空格隔开的正整数 $a_1, a_2, \cdots, a_n$，描述序列。

输出格式

输出到标准输出。

输出一行一个整数，表示不同的合法可重集合数量。

样例

输入

5
1 2 3 1 3

输出

11

解释

合法可重集合有如下 $11$ 种。

$\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 3, 3\} , \{1, 2, 3\}, \{1, 1, 2, 3\}, \{1, 2, 3, 3\}, \{1, 1, 2, 3, 3\}$。

样例

输入

12
1 2 3 4 5 6 5 6 4 3 2 1

输出

50

子任务

对于所有测试数据，$1 \le n \le 5 \times 10^5$，$1 \le a_i \le n$。保证序列中每种数字出现不超过两次。

Subtask 1 (5pts)：$n\leq 100$。

Subtask 2 (15pts)：$n\leq 5000$。

Subtask 3 (25pts)：$n\leq 2 \times 10^5$，特殊性质 1。

Subtask 4 (25pts)：$n\leq 2 \times 10^5$，特殊性质 2。

Subtask 5 (30pts)：无特殊限制。

特殊性质 1：$a_i$ 由另一序列 $b_1, b_2, \cdots, b_n$ 进行如下变换而来：

• 对于每个 $1 \le i \le n$，独立均匀随机生成一个权值 $p_i \in \left[\frac{i}{n} - 10^{-3}, \frac{i}{n}+10^{-3}\right]$。
• 序列 $a$ 是由序列 $b$ 按照权值 $p$ 从小到大排序的结果。即对于每个 $i \in [1, n]$，令 $j$ 满足 $p_{j}$ 是 $p_1, p_2, \cdots, p_n$ 中第 $i$ 小的值，那么有 $a_i=b_{j}$。

特殊性质 2：保证 $n$ 是偶数。保证 $a_{\frac{n}{2}} = n$，且 $a_1, a_2, \cdots, a_{\frac{n}{2}}$ 中的数字各不相同，$a_{\frac{n}{2}}, a_{\frac{n}{2}+1}, \cdots, a_{n}$ 中的数字也各不相同。