Given an integer sequence $a_1, a_2, \cdots, a_{n}$ of length $n$, where each element is between $1$ and $n$, and each number from $1$ to $n$ appears at most twice.
Two multisets $S$ and $T$ are defined as identical if and only if for every $x \in S \cup T$, the number of occurrences of $x$ in $S$ is equal to the number of occurrences of $x$ in $T$. Conversely, two multisets $S$ and $T$ are different if and only if there exists an $x \in S \cup T$ such that the number of occurrences of $x$ in $S$ is not equal to the number of occurrences of $x$ in $T$.
A multiset $S \subseteq \{1, 1, 2, 2, \cdots, n, n\}$ is valid if and only if there exists an interval $[l, r]$ ($1\leq l \leq r \leq n$) such that the multiset $T = \{a_l, a_{l+1}, \cdots, a_r\}$ is identical to $S$.
You need to calculate the number of distinct valid multisets.
Input
The first line contains a positive integer $n$, representing the length of the sequence.
The second line contains $n$ space-separated positive integers $a_1, a_2, \cdots, a_n$, describing the sequence.
Output
Output a single integer representing the number of distinct valid multisets.
Examples
Input 1
5 1 2 3 1 3
Output 1
11
Note 1
The $11$ valid multisets are: $\{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\}$.
Input 2
12 1 2 3 4 5 6 5 6 4 3 2 1
Output 2
50
Subtasks
For all test cases, $1 \le n \le 5 \times 10^5$ and $1 \le a_i \le n$. It is guaranteed that each number appears at most twice in the sequence.
Subtask 1 (5pts): $n\leq 100$.
Subtask 2 (15pts): $n\leq 5000$.
Subtask 3 (25pts): $n\leq 2 \times 10^5$, Special Property 1.
Subtask 4 (25pts): $n\leq 2 \times 10^5$, Special Property 2.
Subtask 5 (30pts): No special restrictions.
Special Property 1: The sequence $a$ is derived from another sequence $b_1, b_2, \cdots, b_n$ through the following transformation: - For each $1 \le i \le n$, independently and uniformly generate a weight $p_i \in \left[\frac{i}{n} - 10^{-3}, \frac{i}{n}+10^{-3}\right]$. - The sequence $a$ is the result of sorting the sequence $b$ according to the weights $p$ in ascending order. That is, for each $i \in [1, n]$, let $j$ be the index such that $p_{j}$ is the $i$-th smallest value among $p_1, p_2, \cdots, p_n$, then $a_i=b_{j}$.
Special Property 2: It is guaranteed that $n$ is even. It is guaranteed that $a_{\frac{n}{2}} = n$, and all numbers in $a_1, a_2, \cdots, a_{\frac{n}{2}}$ are distinct, and all numbers in $a_{\frac{n}{2}}, a_{\frac{n}{2}+1}, \cdots, a_{n}$ are also distinct.