Liên hiệp Bò của Farmer John (UCFJ) đang cử một đoàn đại biểu tham dự Olympic Tin học Bò Quốc tế (IOI).

Có \(N\) con bò tham gia quá trình tuyển chọn (\(1\le N\le2\cdot10^5\)). Chúng đang đứng thành một hàng, và con bò thứ \(i\) thuộc giống \(b_i\).

Đoàn đại biểu sẽ là một đoạn liên tiếp gồm ít nhất ba con bò, tức các con bò \(l\ldots r\) với hai số nguyên \(l\) và \(r\) thỏa mãn \(1\le l<r\le N\) và \(r-l\ge2\). Ba con bò trong đoạn được chọn làm trưởng đoàn. Vì lý do pháp lý, hai con bò ở hai đầu đoạn bắt buộc phải là trưởng đoàn. Ngoài ra, để tránh xung đột trong cùng giống, mỗi trưởng đoàn phải thuộc một giống khác với tất cả thành viên còn lại của đoàn, bất kể thành viên đó có phải 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 đại biểu tham dự IOI. Hai đoàn được coi là khác nhau nếu chúng có thành viên khác nhau hoặc có các trưởng đoàn khác nhau.

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 đoạn \([1,N]\).

Dữ liệu ra

In số đoàn đại biểu có thể chọn trên một dòng.

Lưu ý rằng do các số nguyên trong bài có thể rất lớn, bạn có thể cần dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 1-2 thỏa mãn \(N\le50\).
• Các test 3-4 thỏa mãn \(N\le500\).
• Các test 5-8 thỏa mãn \(N\le5000\).
• Các test 9-20 không có ràng buộc bổ sung.

Ví dụ

7
1 2 3 4 3 2 5

9

Mỗi đoàn đại biểu tương ứng với một trong các bộ ba trưởng đoàn sau:

Nguồn

USACO 2021 US Open, Platinum - United Cows of Farmer John: https://usaco.org/index.php?page=viewproblem2&cpid=1140

Tác giả: Benjamin Qi.