[USACO OPEN 2021 P]United Cows of Farmer John
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

The United Cows of Farmer John (UCFJ) are sending a delegation to the International bOvine olympIad (IOI).

There are N cows participating in delegation selection They are standing in a line, and cow i has breed bi.

The delegation will consist of a contiguous interval of at least three cows - that is, cows l…r for integers l and r satisfying  and . Three of the cows in the chosen interval are marked as delegation leaders. For legal reasons, the two outermost cows of the chosen interval must be leaders. Moreover, to avoid intra-breed conflict, every leader must be of a different breed from the rest of the delegation (leaders or not).

Help the UCFJ determine (for tax reasons) the number of ways they might choose a delegation to send to the IOI. Two delegations are considered different if they have different members or different leaders

输入描述:

The first line contains N.
The second line contains N integers b1,b2,…,bN, each in the range [1,N].

输出描述:

The number of possible delegations, on a single line.
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 long" in C/C++).
示例1

输入

复制 
7
1 2 3 4 3 2 5

输出

复制 
9

说明

Each delegation corresponds to one of the following triples 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).

备注:

Test cases 1-2 satisfy N≤50.
Test cases 3-4 satisfy N≤500.
Test cases 5-8 satisfy N≤5000.
Test cases 9-20 satisfy no additional constraints.