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$。選定區間兩端的乳牛被指定為「領隊」。為避免同品種內部的衝突，每頭領隊的品種必須不同於代表團中其餘所有乳牛的品種（無論是否為領隊）。

請幫助 UCFJ 出於稅務原因確定選出一個代表團參加 IOI 的方案數。

輸入格式

第一行包含 $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