Nene vs. Monsters (Hard Version) - Problem

이 문제는 하드 버전입니다. 두 버전의 유일한 차이점은 $a_i$에 대한 제한 조건입니다. 두 버전의 문제를 모두 해결한 경우에만 해킹을 시도할 수 있습니다.

Nene은 원형으로 배치된 $n$마리의 몬스터와 싸우고 있습니다. 몬스터들은 $1$부터 $n$까지 번호가 매겨져 있으며, $i$번째($1 \le i \le n$) 몬스터의 현재 에너지 레벨은 $a_i$입니다.

몬스터들이 너무 강력하기 때문에, Nene은 이웃 공격(Attack Your Neighbour) 주문을 사용하여 싸우기로 했습니다. Nene이 이 주문을 사용하면, 다음 동작들이 순서대로 하나씩 일어납니다.

에너지 레벨이 $x$인 몬스터가 에너지 레벨이 $y$인 몬스터를 공격하면, 방어하는 몬스터의 에너지 레벨은 $\max(0, y-x)$가 됩니다(공격하는 몬스터의 에너지 레벨은 $x$로 유지됩니다).

Nene은 이 주문을 $10^{100}$번 사용할 예정이며, 주문 사용 후에도 여전히 에너지 레벨이 0이 아닌 몬스터들은 직접 처리할 것입니다. Nene이 주문을 $10^{100}$번 사용한 후, 에너지 레벨이 0이 아닌 몬스터가 누구인지 결정해 주세요.

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수 $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$를 넘지 않음이 보장됩니다.

각 테스트 케이스에 대하여,

첫 번째 줄에는 주문을 $10^{100}$번 사용한 후 에너지 레벨이 0이 아닌 몬스터의 수 $m$을 출력합니다.
두 번째 줄에는 에너지 레벨이 0이 아닌 몬스터들의 인덱스 $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$번 몬스터만 0이 아닌 에너지 레벨을 가집니다.

두 번째 테스트 케이스에서는 두 몬스터 모두 처음에 에너지 레벨이 0입니다.

QOJ.ac