#PU1468. USACO 2025 January Contest, Bronze — Problem 2. It's Mooin' Time II

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

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

题目描述

Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest." Elsie still doesn't understand, so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as an array of NN (1≤N≤1061\le N\le 10^6) integers a1,a2,…,aNa_1, a_2, \dots, a_N (1≤ai≤N1\le a_i\le N). Farmer John defines a moo as an array of three integers where the second integer equals the third but not the first. A moo is said to occur in the contest if it is possible to remove integers from the array until only the moo remains. As Bessie allegedly "mooed all over the contest", help Elsie count the number of distinct moos that occur in the contest! Two moos are distinct if they do not consist of the same integers in the same order.

输入格式

The first line contains NN. The second line contains NN space-separated integers a1,a2,…,aNa_1,a_2,\dots,a_N.

输出格式

(见题面原文)

数据范围

Inputs 2-4: N≤102N\le 10^2 Inputs 5-7: N≤104N\le 10^4 Inputs 8-11: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

6
1 2 3 4 4 4
3
This contest has three distinct moos: "1 4 4", "2 4 4", and "3 4 4".