• Cho mảng \(A\) gồm \(n\) số nguyên dương.

• Một mảng con (gồm những phần tử liên tiếp) của mảng \(A\) gọi là "kì diệu" nếu mỗi số nguyên trong đoạn con đó xuất hiện đúng \(3\) lần.

Yêu cầu: Đếm số lượng mảng con "kì diệu" có trong \(A\).

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 5.10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) với \(1\le a_i\le n\text{ } \forall i=\overline{1,n}\)

Output

• In ra đáp án cần tìm.

Example

8
1 2 3 3 3 2 2 1

2