Это сложная версия задачи. Единственное различие между версиями заключается в ограничениях на $a_i$. Вы можете делать взломы только в том случае, если решены обе версии задачи.

Нене сражается с $n$ монстрами, расположенными по кругу. Монстры пронумерованы от $1$ до $n$, а текущий уровень энергии $i$-го ($1 \le i \le n$) монстра равен $a_i$.

Поскольку монстры слишком сильны, Нене решила сразиться с ними, используя заклинание «Атака соседа». Когда Нене использует это заклинание, происходят следующие действия в указанном порядке одно за другим:

• $1$-й монстр атакует $2$-го монстра;
• $2$-й монстр атакует $3$-го монстра;
• ...
• $(n-1)$-й монстр атакует $n$-го монстра;
• $n$-й монстр атакует $1$-го монстра.

Когда монстр с уровнем энергии $x$ атакует монстра с уровнем энергии $y$, уровень энергии защищающегося монстра становится равным $\max(0, y-x)$ (уровень энергии атакующего монстра остается равным $x$).

Нене собирается использовать это заклинание $10^{100}$ раз, а с монстрами, у которых останется ненулевой уровень энергии, она разберется сама. Вам нужно определить, у каких монстров останется ненулевой уровень энергии после того, как она применит описанное заклинание $10^{100}$ раз.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке содержится количество наборов входных данных $t$ ($1 \le t \le 10^4$). Далее следует описание наборов входных данных.

В первой строке каждого набора содержится целое число $n$ ($2 \le n \le 2 \cdot 10^5$) — количество монстров.

Во второй строке содержится $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — текущие уровни энергии монстров.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $2 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных:

• в первой строке выведите целое число $m$ — количество монстров с ненулевым уровнем энергии после $10^{100}$ применений заклинания;
• во второй строке выведите $m$ целых чисел $i_1, i_2, \ldots, i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) — индексы этих монстров в порядке возрастания.

Если $m=0$, вы можете вывести пустую строку или не выводить её вовсе.

Примеры

Примеры 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

Выходные данные 1

1
1 
0

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

Примечание

В первом наборе входных данных во время первых $3$ применений заклинания происходят следующие действия:

• Нене использует заклинание «Атака соседа» в первый раз;
• $1$-й монстр атакует $2$-го монстра, после атаки уровень энергии $2$-го монстра становится равным $\max(0, 5-2)=3$;
• $2$-й монстр атакует $3$-го монстра, после атаки уровень энергии $3$-го монстра становится равным $\max(0, 3-3)=0$;
• $3$-й монстр атакует $1$-го монстра, после атаки уровень энергии $1$-го монстра становится равным $\max(0, 2-0)=2$;
• Нене использует заклинание «Атака соседа» во второй раз;
• $1$-й монстр атакует $2$-го монстра, после атаки уровень энергии $2$-го монстра становится равным $\max(0, 3-2)=1$;
• $2$-й монстр атакует $3$-го монстра, после атаки уровень энергии $3$-го монстра становится равным $\max(0, 0-1)=0$;
• $3$-й монстр атакует $1$-го монстра, после атаки уровень энергии $1$-го монстра становится равным $\max(0, 2-0)=2$;
• Нене использует заклинание «Атака соседа» в третий раз;
• $1$-й монстр атакует $2$-го монстра, после атаки уровень энергии $2$-го монстра становится равным $\max(0, 1-2)=0$;
• $2$-й монстр атакует $3$-го монстра, после атаки уровень энергии $3$-го монстра становится равным $\max(0, 0-0)=0$;
• $3$-й монстр атакует $1$-го монстра, после атаки уровень энергии $1$-го монстра становится равным $\max(0, 2-0)=2$.

После каждого последующего применения заклинания уровни энергии монстров не меняются. Таким образом, в конце только у $1$-го монстра остается ненулевой уровень энергии.

Во втором наборе входных данных оба монстра изначально имеют нулевой уровень энергии.