這是本題的簡易版。兩個版本之間唯一的區別在於 $a_i$ 的限制。只有在兩個版本的問題都解決的情況下,你才能進行 hacks。
Nene 正在與 $n$ 隻怪物戰鬥,這些怪物位於一個圓圈上。這些怪物編號從 $1$ 到 $n$,第 $i$ 隻 ($1 \le i \le n$) 怪物的當前能量值為 $a_i$。
由於怪物太強大,Nene 決定使用「攻擊你的鄰居」(Attack Your Neighbour)咒語來與牠們戰鬥。當 Nene 使用此咒語時,會依序發生以下動作:
- 第 $1$ 隻怪物攻擊第 $2$ 隻怪物;
- 第 $2$ 隻怪物攻擊第 $3$ 隻怪物;
- ...
- 第 $(n-1)$ 隻怪物攻擊第 $n$ 隻怪物;
- 第 $n$ 隻怪物攻擊第 $1$ 隻怪物。
當能量值為 $x$ 的怪物攻擊能量值為 $y$ 的怪物時,防禦方怪物的能量值會變為 $\max(0, y-x)$(攻擊方怪物的能量值保持為 $x$ 不變)。
Nene 打算使用此咒語 $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 2 \cdot 10^5$),代表怪物的當前能量值。
保證所有測試案例的 $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$ 次使用咒語期間會依序發生以下動作:
- Nene 第一次使用「攻擊你的鄰居」咒語;
- 第 $1$ 隻怪物攻擊第 $2$ 隻怪物,攻擊後第 $2$ 隻怪物的能量值變為 $\max(0, 5-2)=3$;
- 第 $2$ 隻怪物攻擊第 $3$ 隻怪物,攻擊後第 $3$ 隻怪物的能量值變為 $\max(0, 3-3)=0$;
- 第 $3$ 隻怪物攻擊第 $1$ 隻怪物,攻擊後第 $1$ 隻怪物的能量值變為 $\max(0, 2-0)=2$;
- Nene 第二次使用「攻擊你的鄰居」咒語;
- 第 $1$ 隻怪物攻擊第 $2$ 隻怪物,攻擊後第 $2$ 隻怪物的能量值變為 $\max(0, 3-2)=1$;
- 第 $2$ 隻怪物攻擊第 $3$ 隻怪物,攻擊後第 $3$ 隻怪物的能量值變為 $\max(0, 0-1)=0$;
- 第 $3$ 隻怪物攻擊第 $1$ 隻怪物,攻擊後第 $1$ 隻怪物的能量值變為 $\max(0, 2-0)=2$;
- Nene 第三次使用「攻擊你的鄰居」咒語;
- 第 $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$ 隻怪物的能量值不為零。
在第二個測試案例中,兩隻怪物最初的能量值皆為零。