Farmer John đang cố mô tả cuộc thi USACO yêu thích của mình cho Elsie, nhưng cô gặp khó khăn trong việc hiểu tại sao ông lại thích nó đến vậy. Ông nói: "Phần yêu thích của tôi trong cuộc thi là khi Bessie nói 'It's Mooin' Time' rồi rống khắp cuộc thi."

Elsie vẫn không hiểu, nên Farmer John tải cuộc thi xuống dưới dạng một tệp văn bản và cố giải thích ý ông. Cuộc thi được định nghĩa là một mảng gồm \(N\) (\(1\le N\le 10^6\)) số nguyên \(a_1, a_2, \dots, a_N\) (\(1\le a_i\le N\)). Farmer John định nghĩa một tiếng rống (moo) là một mảng gồm ba số nguyên, trong đó số thứ hai bằng số thứ ba nhưng khác số thứ nhất. Một tiếng rống được coi là xuất hiện trong cuộc thi nếu có thể xóa các số nguyên khỏi mảng cho đến khi chỉ còn lại tiếng rống đó.

Vì Bessie được cho là đã "rống khắp cuộc thi", hãy giúp Elsie đếm số tiếng rống phân biệt xuất hiện trong cuộc thi! Hai tiếng rống là phân biệt nếu chúng không gồm cùng các số nguyên theo cùng thứ tự.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(a_1,a_2,\dots,a_N\).

Dữ liệu ra

In số tiếng rống phân biệt xuất hiện trong cuộc thi.

Lưu ý rằng kích thước lớn của các số nguyên trong bài này có thể đòi hỏi sử dụng kiểu dữ liệu số nguyên 64 bit (ví dụ long trong Java, long long trong C/C++).

Ví dụ

6
1 2 3 4 4 4

3

Phân nhóm

• Inputs 2-4: \(N\le 10^2\).
• Inputs 5-7: \(N\le 10^4\).
• Inputs 8-11: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Bronze — It's Mooin' Time II

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1468

Tác giả đề: Benjamin Qi