Liên minh bò của Farmer John (UCFJ) gửi đoàn đại biểu đến International bOvine olympIad (IOI).

Có $N$ con bò tham gia tuyển chọn ($1 \leq N \leq 2 \cdot 10^5$). Chúng đứng thành hàng và bò $i$ có giống $b_i$.

Đoàn gồm một đoạn liên tiếp có ít nhất hai con bò: các con $l\ldots r$ với số nguyên $l$, $r$ thỏa mãn $1\le l<r\le N$. Hai con ở hai đầu đoạn sẽ được chỉ định là « trưởng đoàn ». Để tránh xung đột trong cùng giống, mỗi trưởng đoàn phải khác giống với tất cả thành viên còn lại, dù là trưởng đoàn hay không.

Hãy giúp UCFJ xác định, vì lý do thuế, số cách chọn đoàn gửi đến IOI.

Dữ liệu vào

Dòng đầu tiên chứa $N$.

Dòng thứ hai chứa $N$ số nguyên $b_1,b_2,\ldots,b_N$, mỗi số thuộc khoảng $[1,N]$.

Dữ liệu ra

Số đoàn có thể chọn, trên một dòng.

Các số nguyên lớn có thể cần kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Ví dụ

Dữ liệu vào 1

7
1 2 3 4 3 2 5

Dữ liệu ra 1

13

Ghi chú

Mỗi đoàn tương ứng với một trong các cặp trưởng đoàn sau:

$$(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).$$

Nhiệm vụ con

• Các trường hợp 1–3 thỏa mãn $N\le 100$.
• Các trường hợp 4–8 thỏa mãn $N\le 5000$.
• Các trường hợp 9–20 không có giới hạn bổ sung.

Ghi công bài toán: Benjamin Qi