P7530 [USACO21OPEN] United Cows of Farmer John P

The United Cows of Farmer John (UCFJ) is going to send a team to the International bOvine olympIad (IOI). There are $N$ cows taking part in the team selection. They stand in a line, and cow $i$ has breed $b_i$. The team will be a contiguous interval containing at least three cows—namely, cows $l \dots r$ where $1 \le l < r \le N$ and $r - l \ge 2$. Exactly three cows in the chosen interval will be assigned as leaders. For legal reasons, the two cows at the ends must be leaders. Also, to avoid conflicts within the same breed, each leader must have a breed different from every other member of the team (including the other leaders). Please help UCFJ compute (for tax reasons) the number of ways they can send a team to IOI. If two teams have different members or different leaders, they are considered different.

The first line contains $N$. The second line contains $N$ integers $b_1, b_2, \dots, b_N$, each in the range $[1, N]$.

Output one line with an integer representing the number of possible teams.

#### Sample Explanation Each team corresponds to the following set of leaders: $$(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).$$ #### Constraints $1 \le N \le 2 \times 10^5$ Translated by ChatGPT 5