페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6213
서브태스크

학생회장 후보선출 2s 1024MB

문제

교장선생님은 중요한 작업을 수행해야 합니다 - 몇 번 학생을 학생회장으로 뽑아야 하는지 결정하는 것입니다.

학교의 N명의 학생들 (2 \le N \le 10^5)은 1부터 N까지 번호가 매겨져 있으며, 각 학생는 정확히 한 명의 학생회장 후보 h_i (1 \le h_i \le N)를 지지합니다. 그는 모든 학생들이 같은 후보를 지지하도록 하고 싶어합니다.

이를 위해 교장선생님은 의견 교환을 개최할 수 있습니다. 의견 교환은 번호가 i부터 j까지인 연속된 범위의 모든 학생들을 모아 회의를 하는 것입니다. 만약 그룹 내에서 과반수 이상의 학생들이 지지하는 후보가 있다면, 회의가 끝난 후 모든 학생들은 그 후보를 지지하게 됩니다. 그런 후보가 없다면, 학생들은 지지하는 후보를 바꾸지 않습니다. 예를 들어, 16명의 학생으로 구성된 의견 교환에서는 9명 이상이 같은 후보를 지지해야 나머지 학생들이 그에 맞춰 지지하는 학생을 바꿉니다.

교장선생님은 모든 학생들이 동시에 좋아할 수 있는 후보가 누구인지 알고 싶어합니다. 그는 한 번에 하나의 의견 교환만 개최할 수 있지만, 필요한 만큼 의견 교환을 운영할 수 있습니다.


입력

첫 번째 줄에는 독립적인 테스트 케이스의 수 T가 주어집니다 (1 \leq T \leq 10).

각 테스트 케이스의 첫 번째 줄에는 N이 주어집니다.

두 번째 줄에는 학생들이 지지하는 후보 h_i가 순서대로 주어지는 N개의 정수가 있습니다.

모든 테스트 케이스에 대한 N의 합은 2 \cdot 10^5를 초과하지 않습니다.


출력

각 테스트 케이스에 대해 한 줄씩 출력합니다.

모든 학생들이 동시에 같은 후보를 지지하도록 만들 수 있다면, 가능한 모든 후보를 오름차순으로 출력합니다. 그렇지 않다면, -1을 출력합니다. 같은 줄에 숫자를 출력할 때는 인접한 숫자 사이에 공백을 넣고, 줄 끝에 불필요한 공백이 없어야 합니다.


부분문제

번호 점수 조건
#19점

N = 2

#219점

N \le 50

#329점

h_i ≤ h_{i+1} (1≤i≤N−1)

#443점

추가 제약 조건 없음


예제 

5
5
3 2 2 2 1
6
4 2 3 4 2 3
6
6 6 6 2 2 2
2
2 1
3
3 2 3
2
-1
2 6
-1
3

샘플 입력에서는 5개의 테스트 케이스가 있습니다.

첫 번째 테스트 케이스에서는 모든 학생들이 후보 2를 지지하도록 만드는 것이 가능합니다. 교장선생님은 모든 학생들과 함께 의견 교환을 통해 이를 실행할 수 있습니다.

두 번째 테스트 케이스에서는 학생들이 지지하는 후보를 바꾸지 않는 것을 보여줄 수 있습니다.

세 번째 테스트 케이스에서는 의견 교환을 통해 모든 학생들이 후보 6을 지지하게 만들 수 있으며, 마찬가지로 후보 2도 만들 수 있습니다.

네 번째 테스트 케이스에서는 학생들이 지지하는 후보를 바꾸지 않는 것을 보여줄 수 있습니다.

다섯 번째 테스트 케이스에서는 모든 학생들이 후보 3을 지지하도록 만드는 것이 가능합니다.



출처

USACO 2024 January Bronze

로그인해야 코드를 작성할 수 있어요.