Фермер Джон выстроил \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) своих коров в ряд \(a\).
\(i\)'-ая корова от начала ряда \(a\) помечена целым числом \(a_i\)
(\(1 \leq a_i \leq N\)). Несколько коров могут быть помечены одним и тем же числом.
ФД конструирует ряд \(b\) следующим образом:
- Изначально массив \(b\) пустой.
- Пока массив \(a\) не пустой, удалить первый элемент ряда \(a\) и добавить или не добавить этот элемент в конец массива \(b\).
ФД хочет сконструировать \(b\) так, чтобы последовательность меток в \(b\) от начала
к концу была лексикографически наибольшей.
Прежде чем ФД начнёт конструировать ряд \(b\), он может выполнить следующую
операцию не более чем один раз.
- Выбрать корову в ряду \(a\) и переместить её в любую позицию, кроме текущей.
При условии, что ФД оптимально выполняет эту операцию не более одного раза,
выведите лексикографически наибольшую последовательность \(b\), которую он сможет получить.
Каждый тест состоит из \(T\) (\(1 \leq T \leq 100\)) независимых подтестов.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(T\).
Первая строка каждого подтеста содержит \(N\).
Вторая строка каждого подтеста содержит \(N\) разделённых одиночными
пробелами целых чисел \(a_1, a_2, \ldots, a_N\).
Гарантируется что сумма \(N\) по всем подтестам не превысит \(10^6\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите лексикографически наибольший \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|