E2. Нина против монстров (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

  • $$$1$$$-й монстр атакует $$$2$$$-го монстра;
  • $$$2$$$-й монстр атакует $$$3$$$-го монстра;
  • $$$\ldots$$$
  • $$$(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$$$, вы можете либо вывести пустую строку, либо не выводить ее.

Пример
Входные данные
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 
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$$$-го монстра ненулевой уровень энергии.

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