농부 존의 소 연합

농부 존의 소 연합(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이고 \(r-l\ge 2\)를 만족하는 정수 \(l\)과 \(r\)에 대해 소 \(l\ldots r\)로 구성된다. 선택된 구간의 소 중 세 마리는 대표단 리더로 지정된다. 법적인 이유로, 선택된 구간의 양 끝에 있는 두 소는 반드시 리더여야 한다. 또한 품종 간 갈등을 피하기 위해, 모든 리더는 (리더 여부와 관계없이) 대표단의 나머지 모든 소와 다른 품종이어야 한다.

UCFJ가 IOI에 파견할 대표단을 선택하는 방법의 수를 (세금 문제 때문에) 구하는 것을 도와주자. 두 대표단은 구성원이 다르거나 리더가 다르면 서로 다른 것으로 간주한다.

출제자: Benjamin Qi

채점 방식

• 테스트 케이스 1-2는 \(N\le 50\)을 만족한다.
• 테스트 케이스 3-4는 \(N\le 500\)을 만족한다.
• 테스트 케이스 5-8은 \(N\le 5000\)을 만족한다.
• 테스트 케이스 9-20은 추가 제약이 없다.

출제자: Benjamin Qi

첫째 줄에 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(b_1,b_2,\ldots,b_N\)이 주어지며, 각각 \([1,N]\) 범위에 속한다.

가능한 대표단의 수를 한 줄에 출력한다.

이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > US Open > Platinum