To jest trudniejsza wersja zadania. Jedyną różnicą między wersjami są ograniczenia na $a_i$. Możesz zgłaszać poprawki tylko wtedy, gdy obie wersje zadania zostały rozwiązane.

Nene walczy z $n$ potworami ustawionymi w okrąg. Potwory są ponumerowane od $1$ do $n$, a aktualny poziom energii $i$-tego ($1 \le i \le n$) potwora wynosi $a_i$.

Ponieważ potwory są zbyt silne, Nene postanowiła walczyć z nimi za pomocą zaklęcia Attack Your Neighbour (Atakuj sąsiada). Kiedy Nene używa tego zaklęcia, następujące akcje dzieją się w podanej kolejności jedna po drugiej:

• $1$-szy potwór atakuje $2$-gi potwór;
• $2$-gi potwór atakuje $3$-ci potwór;
• ...
• $(n-1)$-szy potwór atakuje $n$-ty potwór;
• $n$-ty potwór atakuje $1$-szy potwór.

Kiedy potwór o poziomie energii $x$ atakuje potwora o poziomie energii $y$, poziom energii broniącego się potwora staje się równy $\max(0, y-x)$ (poziom energii atakującego potwora pozostaje równy $x$).

Nene zamierza użyć tego zaklęcia $10^{100}$ razy, a potworami, które nadal będą miały niezerowy poziom energii, zajmie się sama. Chce, abyś określił, które potwory będą miały niezerowy poziom energii po tym, jak użyje opisanego zaklęcia $10^{100}$ razy.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^4$). Następnie następuje opis przypadków testowych.

Pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($2 \le n \le 2 \cdot 10^5$) --- liczbę potworów.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) --- aktualne poziomy energii potworów.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego:

• w pierwszej linii wypisz liczbę całkowitą $m$ --- liczbę potworów z niezerowym poziomem energii po $10^{100}$ użyciach zaklęcia;
• w drugiej linii wypisz $m$ liczb całkowitych $i_1, i_2, \ldots, i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) --- indeksy tych potworów w kolejności rosnącej.

Jeśli $m=0$, możesz wypisać pustą linię lub nie wypisywać niczego.

Przykład

Przykład 1

5
3
2 5 3
2
0 0
4
1 5 7 2
4
4 2 1 2
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Wyjście 1

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12

Uwagi

W pierwszym przypadku testowym, podczas pierwszych $3$ użyć zaklęcia zachodzą następujące akcje w tej kolejności:

• Nene używa zaklęcia Attack Your Neighbour po raz pierwszy;
• $1$-szy potwór atakuje $2$-gi potwór, po ataku poziom energii $2$-go potwora staje się równy $\max(0, 5-2)=3$;
• $2$-gi potwór atakuje $3$-ci potwór, po ataku poziom energii $3$-go potwora staje się równy $\max(0, 3-3)=0$;
• $3$-ci potwór atakuje $1$-szy potwór, po ataku poziom energii $1$-go potwora staje się równy $\max(0, 2-0)=2$;
• Nene używa zaklęcia Attack Your Neighbour po raz drugi;
• $1$-szy potwór atakuje $2$-gi potwór, po ataku poziom energii $2$-go potwora staje się równy $\max(0, 3-2)=1$;
• $2$-gi potwór atakuje $3$-ci potwór, po ataku poziom energii $3$-go potwora staje się równy $\max(0, 0-1)=0$;
• $3$-ci potwór atakuje $1$-szy potwór, po ataku poziom energii $1$-go potwora staje się równy $\max(0, 2-0)=2$;
• Nene używa zaklęcia Attack Your Neighbour po raz trzeci;
• $1$-szy potwór atakuje $2$-gi potwór, po ataku poziom energii $2$-go potwora staje się równy $\max(0, 1-2)=0$;
• $2$-gi potwór atakuje $3$-ci potwór, po ataku poziom energii $3$-go potwora staje się równy $\max(0, 0-0)=0$;
• $3$-ci potwór atakuje $1$-szy potwór, po ataku poziom energii $1$-go potwora staje się równy $\max(0, 2-0)=2$.

Po każdym kolejnym użyciu zaklęcia poziomy energii potworów nie zmieniają się. Zatem ostatecznie tylko $1$-szy potwór ma niezerowy poziom energii.

W drugim przypadku testowym oba potwory początkowo mają zerowy poziom energii.