문제
농부 John은 한 줄에 N마리 (1 ≤ N ≤ 2⋅10⁵)의 소를 가지고 있으며, 이 줄을 a라고 합니다. a의 맨 앞에서부터 i번째 소에는 정수 aᵢ (1 ≤ aᵢ ≤ N)가 적혀 있습니다. 여러 소가 같은 숫자를 가질 수도 있습니다.
농부 John은 다음과 같이 새로운 줄 b를 구성하려고 합니다:
처음에 b는 비어 있습니다.
a가 비어있지 않은 동안, a의 맨 앞 소를 제거하고 그 소를 b의 뒤쪽에 추가할지 결정합니다.
John은 b에 적힌 소들의 번호가 앞에서부터 읽었을 때 사전 순(lexicographically)으로 가장 큰 수열이 되도록 하고자 합니다.
b를 구성하기 전에, John은 다음 연산을 최대 한 번 수행할 수 있습니다:
a에 있는 한 마리의 소를 선택하여, 현재 위치보다 앞쪽의 아무 위치로든 옮깁니다.
John이 이 연산을 최적으로 최대 한 번 수행했을 때, 얻을 수 있는 사전 순으로 가장 큰 b 수열을 출력하세요.
각 입력은 T (1 ≤ T ≤ 100)개의 독립적인 테스트 케이스로 구성됩니다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어집니다.
각 테스트 케이스에 대해, 첫 번째 줄에는 정수 N이 주어집니다.
두 번째 줄에는 N개의 정수 a₁, a₂, …, aₙ이 공백으로 구분되어 주어지며, 이는 소에 적힌 번호를 나타냅니다.
모든 테스트 케이스에서 N의 합은 10⁶을 넘지 않습니다.
출력
각 테스트 케이스마다, 사전 순으로 가장 큰 b 수열을 한 줄에 출력하세요. (각 수는 공백으로 구분합니다.)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | |
| #3 | 50점 | 추가 제약 없음 |
예제1
3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1
4 3 3 2 1
6 5 4
4 3 2 1 1
첫 번째 테스트 케이스에서, John은 다섯 번째 소를 두 번째 소 바로 뒤로 옮길 수 있습니다. 이렇게 하면 a = [4, 3, 3, 2, 1]이 되고, 이 수열이 사전 순으로 가장 큰 b 수열임을 확인할 수 있습니다.
두 번째 테스트 케이스에서는, John이 네 번째 소를 줄의 맨 앞으로 옮기면 최적의 b 수열을 만들 수 있습니다.
세 번째 테스트 케이스에서는, 어떠한 연산도 수행할 필요 없이, a에 있는 소들을 순서대로 b에 추가하면 사전 순으로 가장 큰 b 수열을 얻을 수 있습니다.