Dany jest ciąg liczb całkowitych $a_1, a_2, \cdots, a_{n}$ o długości $n$, w którym każdy element jest nie mniejszy niż $1$ i nie większy niż $n$, a każda liczba od $1$ do $n$ występuje co najwyżej dwa razy.

Dwa multizbiory $S$ i $T$ nazywamy takimi samymi wtedy i tylko wtedy, gdy dla każdego $x \in S \cup T$ liczba wystąpień $x$ w $S$ jest równa liczbie wystąpień $x$ w $T$. W przeciwnym razie, dwa multizbiory $S$ i $T$ nazywamy różnymi.

Multizbiór $S \subseteq \{1, 1, 2, 2, \cdots, n, n\}$ nazywamy poprawnym wtedy i tylko wtedy, gdy istnieje przedział $[l, r]\ (1\leq l \leq r \leq n)$ taki, że multizbiór $T = \{a_l, a_{l+1}, \cdots, a_r\}$ jest taki sam jak $S$.

Oblicz, ile istnieje różnych poprawnych multizbiorów.

Wejście

Dane są wczytywane ze standardowego wejścia.

Pierwsza linia zawiera liczbę całkowitą dodatnią $n$, oznaczającą długość ciągu.

Druga linia zawiera $n$ liczb całkowitych dodatnich $a_1, a_2, \cdots, a_n$ oddzielonych spacjami, opisujących ciąg.

Wyjście

Wypisz na standardowe wyjście jedną liczbę całkowitą, oznaczającą liczbę różnych poprawnych multizbiorów.

Przykład

Wejście 1

5
1 2 3 1 3

Wyjście 1

11

Uwagi

Istnieje $11$ poprawnych multizbiorów: $\{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\}$.

Wejście 2

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

Wyjście 2

50

Podzadania

Dla wszystkich danych testowych $1 \le n \le 5 \times 10^5$ oraz $1 \le a_i \le n$. Gwarantuje się, że każda liczba w ciągu występuje co najwyżej dwa razy.

Podzadanie 1 (5 pkt): $n\leq 100$.

Podzadanie 2 (15 pkt): $n\leq 5000$.

Podzadanie 3 (25 pkt): $n\leq 2 \times 10^5$, własność specjalna 1.

Podzadanie 4 (25 pkt): $n\leq 2 \times 10^5$, własność specjalna 2.

Podzadanie 5 (30 pkt): Brak dodatkowych ograniczeń.

Własność specjalna 1: Ciąg $a$ powstał z innego ciągu $b_1, b_2, \cdots, b_n$ poprzez następującą transformację: - Dla każdego $1 \le i \le n$ wygenerowano niezależnie i jednostajnie losową wagę $p_i \in \left[\frac{i}{n} - 10^{-3}, \frac{i}{n}+10^{-3}\right]$. - Ciąg $a$ jest wynikiem posortowania ciągu $b$ według wag $p$ w porządku rosnącym. Oznacza to, że dla każdego $i \in [1, n]$, jeśli $j$ jest indeksem, dla którego $p_{j}$ jest $i$-tą najmniejszą wartością wśród $p_1, p_2, \cdots, p_n$, to $a_i=b_{j}$.

Własność specjalna 2: Gwarantuje się, że $n$ jest liczbą parzystą. Gwarantuje się, że $a_{\frac{n}{2}} = n$, liczby w $a_1, a_2, \cdots, a_{\frac{n}{2}}$ są parami różne, a liczby w $a_{\frac{n}{2}}, a_{\frac{n}{2}+1}, \cdots, a_{n}$ również są parami różne.