Дан целочисленный массив $a_1, a_2, \cdots, a_{n}$ длины $n$, где каждый элемент не меньше $1$ и не больше $n$, при этом каждое число от $1$ до $n$ встречается не более двух раз.

Два мультимножества $S$ и $T$ называются одинаковыми тогда и только тогда, когда для любого $x \in S \cup T$ количество вхождений $x$ в $S$ совпадает с количеством вхождений $x$ в $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$, разделенных пробелами, описывающих последовательность.

Выходные данные

Выведите в стандартный вывод одно целое число — количество различных допустимых мультимножеств.

Примеры

Пример 1

Входные данные 1

5
1 2 3 1 3

Выходные данные 1

11

Примечание 1

Существует $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\}$.

Пример 2

Входные данные 2

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

Выходные данные 2

50

Подзадачи

Для всех тестовых данных $1 \le n \le 5 \times 10^5$, $1 \le a_i \le n$. Гарантируется, что каждое число в последовательности встречается не более двух раз.

Подзадача 1 (5 баллов): $n\leq 100$.

Подзадача 2 (15 баллов): $n\leq 5000$.

Подзадача 3 (25 баллов): $n\leq 2 \times 10^5$, выполняется особое свойство 1.

Подзадача 4 (25 баллов): $n\leq 2 \times 10^5$, выполняется особое свойство 2.

Подзадача 5 (30 баллов): Без дополнительных ограничений.

Особое свойство 1: Последовательность $a$ получена из другой последовательности $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}$ является $i$-м по величине значением среди $p_1, p_2, \cdots, p_n$, то $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}$ также различны.