Dla elementu w tablicy, jeśli jest niezerowy i ściśle większy od wszystkich poprzedzających go elementów, to jest uważany za piękny element. Piękno tablicy definiujemy jako liczbę pięknych elementów w tablicy.

Dana jest permutacja długości $n$. Chcesz zmaksymalizować jej piękno, zamieniając niektóre z pięknych elementów na zero. Zauważ, że niektóre elementy mogą stać się piękne po twojej operacji i będą dostępne jako cel kolejnej operacji.

Ponieważ modyfikowanie tablicy jest męczące, decydujesz się zmaksymalizować piękno tablicy, wykonując minimalną możliwą liczbę operacji.

Jeśli istnieje wiele rozwiązań, wypisz dowolne.

Wejście

Istnieje wiele zestawów testowych.

Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \leq t \leq 10^6$), oznaczającą liczbę zestawów testowych. Dla każdego zestawu testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \leq n \leq 10^6$), oznaczającą rozmiar permutacji.

Następny wiersz zawiera $n$ liczb całkowitych $p_i$ ($1 \leq p_i \leq n$), oznaczających elementy permutacji. Gwarantuje się, że wszystkie $p_i$ w jednym zestawie testowym są różne.

Gwarantuje się, że $\sum n \leq 10^6$.

Wyjście

Dla każdego zestawu testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $b, c$, oznaczające maksymalne piękno zmodyfikowanej tablicy oraz minimalną liczbę operacji.

Drugi wiersz zawiera $c$ liczb całkowitych $o_i$, oznaczających ciąg operacji. Operacja $o_i$ oznacza zmianę $o_i$-tego elementu na zero. Powinieneś upewnić się, że $o_i$-ty element jest piękny przed twoją $i$-tą operacją.

Jeśli istnieje wiele rozwiązań, wypisz dowolne.

Przykład

Wejście 1

2
3
3 1 2
3
1 2 3

Wyjście 1

2 1
1
3 0