Phái Đoàn Bò

Cho dãy $N$ con bò xếp thành hàng, con bò thứ $i$ thuộc giống $b_i$. Một phái đoàn là một đoạn liên tiếp $[l,r]$ ($l<r$) gồm ít nhất 2 con bò, trong đó hai con bò ở hai đầu ($l$ và $r$) được chọn làm trưởng đoàn.

Điều kiện: Mỗi trưởng đoàn phải thuộc giống khác với tất cả các con bò còn lại trong phái đoàn. Cụ thể:

• Giống của bò $l$ không xuất hiện trong đoạn $[l+1,r]$
• Giống của bò $r$ không xuất hiện trong đoạn $[l,r-1]$

Hãy đếm số phái đoàn hợp lệ.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: $N$ số nguyên $b_1,b_2,\dots ,b_N$

Dữ liệu ra

Một số nguyên duy nhất: số phái đoàn hợp lệ.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $1\le b_i\le N$
• Kết quả có thể cần kiểu 64-bit

Ví dụ