Farmer John の牛連合（UCFJ）は International bOvine olympIad（IOI）へ代表団を派遣します。

$N$ 頭の牛が代表団の選考に参加します（$1 \leq N \leq 2 \cdot 10^5$）。牛たちは一列に並び、牛 $i$ の品種は $b_i$ です。

代表団は少なくとも二頭からなる連続区間、つまり $1\le l<r\le N$ を満たす整数 $l$ と $r$ に対する牛 $l\ldots r$ で構成されます。選んだ区間の両端の牛を「リーダー」とします。同品種内の対立を避けるため、各リーダーは代表団の他のすべての牛（リーダーかどうかを問わず）と異なる品種でなければなりません。

税務上の理由から、IOI に送る代表団の選び方の数を UCFJ のために求めてください。

入力

最初の行には $N$ が与えられます。

二行目には $N$ 個の整数 $b_1,b_2,\ldots,b_N$ が与えられ、各値は $[1,N]$ の範囲内です。

出力

可能な代表団の数を一行に出力してください。

本問の整数は大きいため、64 ビット整数型（例えば C/C++ の long long）が必要になる場合があります。

入出力例

入力 1

7
1 2 3 4 3 2 5

出力 1

13

注記

各代表団は次のいずれかのリーダーの組に対応します。

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

小課題

• テストケース 1–3 は $N\le 100$ を満たします。
• テストケース 4–8 は $N\le 5000$ を満たします。
• テストケース 9–20 に追加の制約はありません。

問題のクレジット：Benjamin Qi