#PU1140. USACO 2021 US Open, Platinum — Problem 1. United Cows of Farmer John

USACO 2021 US Open, Platinum — Problem 1. United Cows of Farmer John

USACO 2021 US Open, Platinum — Problem 1. United Cows of Farmer John

题目描述

The United Cows of Farmer John (UCFJ) are sending a delegation to the International bOvine olympIad (IOI). There are NN cows participating in delegation selection (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^5). They are standing in a line, and cow ii has breed bib_i. The delegation will consist of a contiguous interval of at least three cows - that is, cows l…rl\ldots r for integers ll and rr satisfying 1≤l<r≤N1\le l<r\le N and r−l≥2r-l\ge 2. 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 NN. The second line contains NN integers b1,b2,…,bNb_1,b_2,\ldots,b_N, each in the range [1,N][1,N].

输出格式

The number of possible delegations, on a single line.

数据范围

Test cases 1-2 satisfy N≤50N\le 50. Test cases 3-4 satisfy N≤500N\le 500. Test cases 5-8 satisfy N≤5000N\le 5000. Test cases 9-20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 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).$$

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).