Это сложная версия задачи. Единственное отличие между версиями — ограничение на \(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}\) раз.
Выходные данные
Для каждого набора входных данных
- в первой строке выведите целое число \(m\) — количество монстров с ненулевым уровнем энергии после \(10^{100}\) использований заклинания;
- во второй строке выведите \(m\) целых чисел \(i_1,i_2,\ldots,i_m\) (\(1 \le i_1 < i_2 < \ldots < i_m \le n\)) — индексы этих монстров в порядке возрастания.
Если \(m=0\), вы можете либо вывести пустую строку, либо не выводить ее.
Примечание
В первом наборе входных данных в первые \(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\)-го монстра ненулевой уровень энергии.
Во втором наборе входных данных у обоих монстров изначально нулевой уровень энергии.
Примеры
| № | Входные данные | Выходные данные |
|
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
0
1
1
2
1 3
6
1 3 6 8 10 12
|