Chọn nhóm

Một hội học sinh vừa thành lập và đang chuẩn bị tổ chức một sự kiện lớn tại trường. Nhà trường gửi cho hội một danh sách gồm \(N\) học sinh, được đánh số từ \(1\) đến \(N\), người thứ \(i\) đến từ lớp \(a[i]\).

Hội cần chọn ra một nhóm học sinh; một nhóm là các học sinh liên tiếp nhau trong danh sách của trường. Khi đó một nhóm là những học sinh từ \(l\) đến \(r\). Tuy nhiên, việc thành lập nhóm phải thỏa mãn các yêu cầu sau:

• Một nhóm có tối thiểu \(3\) thành viên.
• Một nhóm có chính xác \(3\) đội trưởng, \(2\) trong số đó là học sinh \(l\) và \(r\).
• Lớp của \(3\) đội trưởng là phân biệt, và không có học sinh nào trong nhóm thuộc cùng lớp với \(1\) trong \(3\) đội trưởng.

\textbf Yêu cầu: Hãy đếm số nhóm có thể tạo ra. Hai nhóm được xem là khác nhau nếu tập hợp học sinh trong \(2\) nhóm là khác nhau hoặc tập đội trưởng của \(2\) nhóm là khác nhau.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \leq N \leq 2 \times 10^5)\), là số học sinh trong danh sách.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq N)\), trong đó \(a_i\) biểu thị lớp của học sinh thứ \(i\).

Output

In ra một số nguyên duy nhất, là số cách chọn một nhóm học sinh thỏa mãn yêu cầu.

Example

7
1 2 3 4 3 2 5

9

Scoring

• Có \(20\%\) số điểm ứng với \(N \le 500\).
• Có \(30\%\) số điểm ứng với \(N \le 5000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.