給定一個長度為 $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$，描述序列。
輸出格式
輸出到標準輸出。
輸出一行一個整數，表示不同的合法可重集合數量。
範例
輸入 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
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$。保證序列中每種數字出現不超過兩次。
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}$ 中的數字也各不相同。