레이팅 미적용농부 존의 소 연합(United Cows of Farmer John, UCFJ)은 국제 소 올림피아드(International bOvine olympIad, IOI)에 대표단을 파견하려 한다.
대표단 선발에는 소 \(N\)마리(\(1 \leq N \leq 2 \cdot 10^5\))가 참가한다. 소들은 한 줄로 서 있으며, 소 \(i\)의 품종은 \(b_i\)이다.
대표단은 최소 두 마리 이상의 연속된 구간의 소들, 즉 \(1\le l
UCFJ가 (세금 문제로) IOI에 보낼 대표단을 선택할 수 있는 방법의 수를 구하는 것을 도와주자.
문제 제공: Benjamin Qi
채점 방식
- 테스트 케이스 1-3은 \(N\le 100\)을 만족한다.
- 테스트 케이스 4-8은 \(N\le 5000\)을 만족한다.
- 테스트 케이스 9-20은 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 각각 \([1,N]\) 범위인 \(N\)개의 정수 \(b_1,b_2,\ldots,b_N\)이 주어진다.
가능한 대표단의 수를 한 줄에 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.
7
1 2 3 4 3 2 513Each delegation corresponds to one of the following pairs of leaders:
$$ (1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7). $$