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.