Cho dãy số gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ có giá trị thuộc tập hợp ~\{0, 1, 2, 3\}~.

Yêu cầu: Đếm số lượng các đoạn con gồm các số nguyên liên tiếp của dãy số sao cho:

• Gồm đúng ba loại giá trị;

• Số lần xuất hiện của các loại giá trị bằng nhau.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(N \le 10^6)~ là số lượng số trong dãy;

• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(0 \le A_i \le 3)~ mô tả dãy số.

Output

Một dòng duy nhất gồm một số nguyên là số đoạn con thoả mãn.

Scoring

Sample Input 1

11
0 1 2 1 2 0 3 1 0 3 1

Sample Output 1

9

Notes

• Có ~7~ đoạn con độ dài ~3~ thoả mãn là: ~[0, 1, 2]~, ~[1, 2, 0]~, ~[2, 0, 3]~, ~[0, 3, 1]~, ~[3, 1, 0]~, ~[1, 0, 3]~, ~[0, 3, 1]~.

• Có ~2~ đoạn con độ dài ~6~ thoả mãn là: ~[0, 1, 2, 1, 2, 0]~, ~[0, 3, 1, 0, 3, 1]~.

• Tổng có ~9~ đoạn con thỏa mãn.