음머의 시간 II

농부 존은 자신이 가장 좋아하는 USACO 대회를 엘시에게 설명하려 하지만, 엘시는 그가 왜 그렇게 그 대회를 좋아하는지 이해하지 못하고 있다. 그가 말하길, "대회에서 내가 가장 좋아했던 부분은 베시가 '음머의 시간이다(It's Mooin' Time)'라고 말하며 대회 곳곳에 음머를 남겼을 때였어."

엘시가 여전히 이해하지 못하자, 농부 존은 대회를 텍스트 파일로 내려받아 자신이 무슨 뜻으로 말했는지 설명하려 한다. 대회는 \(N\)(\(1\le N\le 10^6\))개의 정수 \(a_1, a_2, \dots, a_N\)(\(1\le a_i\le N\))으로 이루어진 배열로 정의된다. 농부 존은 음머(moo)를 두 번째 정수와 세 번째 정수가 같고 첫 번째 정수는 그와 다른, 세 정수의 배열로 정의한다. 배열에서 정수들을 제거하여 그 음머만 남길 수 있다면, 그 음머가 대회에 나타난다고 한다.

베시가 "대회 곳곳에 음머를 남겼다"고 하니, 대회에 나타나는 서로 다른 음머의 개수를 세는 것을 엘시가 도와주자! 두 음머가 같은 정수들을 같은 순서로 포함하지 않으면 서로 다른 것이다.

문제 제공: Benjamin Qi

배점

• 입력 2-4: \(N\le 10^2\)
• 입력 5-7: \(N\le 10^4\)
• 입력 8-11: 추가 제약 없음.

문제 제공: Benjamin Qi

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

둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(a_1,a_2,\dots,a_N\)이 주어진다.

대회에 나타나는 서로 다른 음머의 개수를 출력한다.

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

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Bronze