ez_code   2년 전

문제

농부 존은 중요한 할 일이 있습니다 - 소를 위해 무슨 건초를 살지 정하는 것이죠.

농부 존의 소 N마리는 1번부터 N번까지 번호가 매겨져 있고 (2 <= N <= 105), 각 소는 하나의 건초 hi를 좋아합니다 (1 <= hi <= N). 농부 존은 모든 소가 같은 건초를 좋아하도록 만들고 싶습니다.

목표를 달성하기 위해, 농부 존은 표본 집단을 소집할 수 있습니다. 표본 집단은 i 이상 j 이하 연속된 범위에 있는 모든 소를 모아 형성됩니다. 만약 집단의 절반이 넘는 소가 좋아하는 건초가 존재한다면, 집단 소집 후 그 집단의 모든 소는 그 건초를 좋아하게 됩니다. 그런 건초가 없다면, 어떤 소도 자신이 좋아하는 건초를 바꾸지 않습니다. 예를 들어, 16마리 소를 소집해 만든 표본 집단이 있다고 하면, 9마리 이상의 소가 같은 건초를 좋아해야 나머지 소의 취향을 그에 맞게 바꿀 수 있습니다.

농부 존은 모든 소가 동시에 좋아하게 될 수 있는 건초를 알고 싶습니다. 그는 한 번에 하나의 표본 집단만 소집할 수 있지만, 모든 소가 같은 건초를 좋아하게 만들기 위해 몇 번이고 표본 집단을 소집할 수 있습니다.

입력

첫 줄에 서로 다른 테스트 케이스의 수를 나타내는 정수 T가 주어집니다. (1 <= T <= 10)

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

둘째 줄은 순서대로 각 소가 좋아하는 건초 hi를 나타내는 N개의 정수가 주어집니다.

모든 테스트케이스의 N의 합이 2 X 105이 넘지 않음이 보장됩니다.

출력

테스트 케이스마다 한 줄에 하나씩, 총 T개의 줄을 출력합니다.

모든 소가 같은 건초를 좋아하게 만들 수 있다면, 가능한 모든 건초를 오름차순으로 출력합니다. 그 외의 경우, -1을 출력합니다. 같은 줄에 숫자를 출력할 때, 각각의 번호를 공백 하나로 구분하고 줄이 관련 없는 공백으로 끝나지 않도록 합니다.

댓글을 작성하려면 로그인해야 합니다.