bronze_Its_Mooin_Time_II (USACO January_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: implementation, data structures, hash map

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
$N$ ($1\le N\le 10^6$) integers $a_1, a_2, \dots, a_N$ ($1\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.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $N$.
The second line contains $N$ space-separated integers $a_1,a_2,\dots,a_N$.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the number of distinct moos that occur in the contest.
**Note that the large size of integers involved in this problem may require
the use of 64-bit integer data types (e.g., a "long" in Java, a "long long" in
C/C++).**
SAMPLE INPUT:
6
1 2 3 4 4 4
SAMPLE OUTPUT:
3
This contest has three distinct moos: "1 4 4", "2 4 4", and "3 4 4".
SCORING:
Inputs 2-4: $N\le 10^2$
Inputs 5-7: $N\le 10^4$
Inputs 8-11: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: