Unique Breed Leader Selection

Farmer John’s United Cows of Farmer John (UCFJ) is selecting a team to participate in the International bOvine olympIad (IOI). There are N cows standing in a line, and the breed of cow i is given by b_i.

A team is defined by a contiguous interval of at least three cows. In the chosen interval (cows from index l to r with 1 ≤ l < r ≤ N and r − l ≥ 2), three cows will be designated as leaders. For legal reasons, the cows at the two ends of the interval (positions l and r) must be leaders. In addition, to avoid intra‐breed conflicts, every leader must have a breed that does not appear elsewhere in the team (including among the other leaders). In other words, if a cow at position i is chosen as a leader in an interval, then the total count of cows with breed b_i in that interval must be exactly one.

Determine the number of ways to select a team and designate the three leaders such that the above conditions hold. Two ways are considered different if the set of team members or the selection of leaders differs.

Note on the uniqueness condition: For an interval [l, r] and a chosen leader at position i (where i equals l, r, or an index between them chosen as the third leader), if we denote by \( freq(b_i) \) the frequency of breed \( b_i \) in that interval, then the condition requires that:

\[ freq(b_i) = 1 \quad \text{for each leader } i\in\{l, r, k\}\,. \]

inputFormat

The first line contains an integer N, the number of cows. The second line contains N space‐separated integers, where the i-th integer denotes the breed b_i of the i-th cow.

outputFormat

Output a single integer, the number of valid ways to select a team and designate three leaders under the given conditions.

sample

3
1 2 3

1