長さ $n$ の整数列 $a_1, a_2, \cdots, a_{n}$ が与えられます。ここで、各要素は $1$ 以上 $n$ 以下であり、$1$ から $n$ までの各数字は最大で2回までしか出現しません。
2つの多重集合 $S, T$ が同じであるとは、任意の $x \in S \cup T$ に対して、$S$ と $T$ における $x$ の出現回数が等しいことを指します。逆に、2つの多重集合 $S, T$ が異なるとは、ある $x \in S \cup T$ が存在して、$S$ と $T$ における $x$ の出現回数が異なることを指します。
多重集合 $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$ と同じになることを指します。
存在する異なる合法な多重集合の個数を求めてください。
入力
標準入力からデータを読み込みます。
1行目に正整数 $n$ が与えられ、数列の長さを表します。
2行目に $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
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$ を満たします。数列内の各数字の出現回数は2回以下であることが保証されます。
小課題 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_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]$ に対して、$p_j$ が $p_1, p_2, \cdots, p_n$ の中で $i$ 番目に小さい値となるような $j$ を選ぶと、$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}$ に含まれる数字もすべて異なることが保証される。