これはこの問題のハードバージョンです。このバージョンとイージーバージョンの唯一の違いは $a_i$ に関する制約です。両方のバージョンを解いた場合にのみハックを行うことができます。

Nene は円状に配置された $n$ 体のモンスターと戦っています。これらのモンスターには $1$ から $n$ までの番号が振られており、$i$ 番目 ($1 \le i \le n$) のモンスターの現在のエネルギーレベルは $a_i$ です。

モンスターは非常に強力であるため、Nene は「隣人を攻撃せよ (Attack Your Neighbour)」という呪文を使って戦うことにしました。Nene がこの呪文を使うと、以下の行動が順番に 1つずつ 発生します。

• $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$) が含まれます。

2 行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) が含まれます。これはモンスターの現在のエネルギーレベルです。

すべてのテストケースにおける $n$ の総和は $2 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースについて、

• 1 行目に、$10^{100}$ 回の呪文使用後にエネルギーレベルがゼロではないモンスターの数 $m$ を出力してください。
• 2 行目に、$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 回目の「隣人を攻撃せよ」を使用する。
• 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 が 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$ になる。
• Nene が 3 回目の「隣人を攻撃せよ」を使用する。
• 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 番目のモンスターのみです。

2 番目のテストケースでは、両方のモンスターが最初からエネルギーレベル 0 を持っています。