Esta es la versión difícil del problema. La única diferencia entre las versiones son las restricciones sobre $a_i$. Solo puedes realizar hacks si ambas versiones del problema están resueltas.

Nene está luchando contra $n$ monstruos, situados en un círculo. Estos monstruos están numerados del $1$ al $n$, y el nivel de energía actual del $i$-ésimo monstruo ($1 \le i \le n$) es $a_i$.

Dado que los monstruos son demasiado fuertes, Nene decidió luchar contra ellos usando el hechizo Attack Your Neighbour (Ataca a tu vecino). Cuando Nene usa este hechizo, las siguientes acciones ocurren en el orden indicado, una por una:

• El $1$-er monstruo ataca al $2$-do monstruo;
• El $2$-do monstruo ataca al $3$-er monstruo;
• ...
• El $(n-1)$-ésimo monstruo ataca al $n$-ésimo monstruo;
• El $n$-ésimo monstruo ataca al $1$-er monstruo.

Cuando el monstruo con nivel de energía $x$ ataca al monstruo con nivel de energía $y$, el nivel de energía del monstruo defensor se convierte en $\max(0, y-x)$ (el nivel de energía del monstruo atacante permanece igual a $x$).

Nene va a usar este hechizo $10^{100}$ veces y se encargará ella misma de los monstruos que aún tengan un nivel de energía distinto de cero. Ella quiere que determines qué monstruos tendrán un nivel de energía distinto de cero una vez que haya usado el hechizo descrito $10^{100}$ veces.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^4$). A continuación se describe cada caso de prueba.

La primera línea contiene un solo entero $n$ ($2 \le n \le 2 \cdot 10^5$) --- el número de monstruos.

La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) --- los niveles de energía actuales de los monstruos.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2 \cdot 10^5$.

Salida

Para cada caso de prueba:

• en la primera línea, imprime un entero $m$ --- el número de monstruos con nivel de energía distinto de cero después de $10^{100}$ usos del hechizo;
• en la segunda línea, imprime $m$ enteros $i_1, i_2, \ldots, i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) --- los índices de estos monstruos en orden creciente.

Si $m=0$, puedes imprimir una línea vacía o no imprimir nada.

Ejemplos

Entrada 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

Salida 1

1
1 
0

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

Nota

En el primer caso de prueba, las siguientes acciones ocurren durante los primeros $3$ usos del hechizo en este orden:

• Nene usa el hechizo Attack Your Neighbour por primera vez;
• el $1$-er monstruo ataca al $2$-do monstruo, después del ataque el nivel de energía del $2$-do monstruo se vuelve igual a $\max(0, 5-2)=3$;
• el $2$-do monstruo ataca al $3$-er monstruo, después del ataque el nivel de energía del $3$-er monstruo se vuelve igual a $\max(0, 3-3)=0$;
• el $3$-er monstruo ataca al $1$-er monstruo, después del ataque el nivel de energía del $1$-er monstruo se vuelve igual a $\max(0, 2-0)=2$;
• Nene usa el hechizo Attack Your Neighbour por segunda vez;
• el $1$-er monstruo ataca al $2$-do monstruo, después del ataque el nivel de energía del $2$-do monstruo se vuelve igual a $\max(0, 3-2)=1$;
• el $2$-do monstruo ataca al $3$-er monstruo, después del ataque el nivel de energía del $3$-er monstruo se vuelve igual a $\max(0, 0-1)=0$;
• el $3$-er monstruo ataca al $1$-er monstruo, después del ataque el nivel de energía del $1$-er monstruo se vuelve igual a $\max(0, 2-0)=2$;
• Nene usa el hechizo Attack Your Neighbour por tercera vez;
• el $1$-er monstruo ataca al $2$-do monstruo, después del ataque el nivel de energía del $2$-do monstruo se vuelve igual a $\max(0, 1-2)=0$;
• el $2$-do monstruo ataca al $3$-er monstruo, después del ataque el nivel de energía del $3$-er monstruo se vuelve igual a $\max(0, 0-0)=0$;
• el $3$-er monstruo ataca al $1$-er monstruo, después del ataque el nivel de energía del $1$-er monstruo se vuelve igual a $\max(0, 2-0)=2$.

Después de cada uno de los siguientes usos del hechizo, los niveles de energía de los monstruos no cambian. Por lo tanto, solo el $1$-er monstruo tiene un nivel de energía distinto de cero al final.

En el segundo caso de prueba, ambos monstruos tienen inicialmente un nivel de energía de cero.