Đây là phiên bản khó của bài toán. Sự khác biệt duy nhất giữa các phiên bản là giới hạn của $a_i$. Bạn chỉ có thể thực hiện hack nếu cả hai phiên bản của bài toán đều đã được giải.

Nene đang chiến đấu với $n$ con quái vật, được xếp thành một vòng tròn. Những con quái vật này được đánh số từ $1$ đến $n$, và mức năng lượng hiện tại của con quái vật thứ $i$ ($1 \le i \le n$) là $a_i$.

Vì các con quái vật quá mạnh, Nene quyết định chiến đấu với chúng bằng phép thuật Attack Your Neighbour (Tấn công hàng xóm). Khi Nene sử dụng phép thuật này, các hành động sau đây sẽ xảy ra theo thứ tự từng bước một:

• Con quái vật thứ $1$ tấn công con quái vật thứ $2$;
• Con quái vật thứ $2$ tấn công con quái vật thứ $3$;
• ...
• Con quái vật thứ $(n-1)$ tấn công con quái vật thứ $n$;
• Con quái vật thứ $n$ tấn công con quái vật thứ $1$.

Khi con quái vật có mức năng lượng $x$ tấn công con quái vật có mức năng lượng $y$, mức năng lượng của con quái vật phòng thủ sẽ trở thành $\max(0, y-x)$ (mức năng lượng của con quái vật tấn công vẫn giữ nguyên là $x$).

Nene dự định sử dụng phép thuật này $10^{100}$ lần và tự mình giải quyết những con quái vật vẫn còn mức năng lượng khác không. Cô ấy muốn bạn xác định những con quái vật nào sẽ có mức năng lượng khác không sau khi cô ấy sử dụng phép thuật đã mô tả $10^{100}$ lần.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $t$ ($1 \le t \le 10^4$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên chứa một số nguyên duy nhất $n$ ($2 \le n \le 2 \cdot 10^5$) --- số lượng quái vật.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) --- mức năng lượng hiện tại của các quái vật.

Đảm bảo rằng tổng của $n$ trên tất cả các trường hợp thử nghiệm không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

Đối với mỗi trường hợp thử nghiệm:

• ở dòng đầu tiên, in ra một số nguyên $m$ --- số lượng quái vật có mức năng lượng khác không sau $10^{100}$ lần sử dụng phép thuật;
• ở dòng thứ hai, in ra $m$ số nguyên $i_1, i_2, \ldots, i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) --- chỉ số của những con quái vật này theo thứ tự tăng dần.

Nếu $m=0$, bạn có thể in một dòng trống hoặc không in gì cả.

Ví dụ

Ví dụ 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

Kết quả 1

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12

Ghi chú

Trong trường hợp thử nghiệm đầu tiên, các hành động sau đây xảy ra trong $3$ lần sử dụng phép thuật đầu tiên theo thứ tự này:

• Nene sử dụng phép thuật Attack Your Neighbour lần thứ nhất;
• con quái vật thứ $1$ tấn công con quái vật thứ $2$, sau đòn tấn công, mức năng lượng của con quái vật thứ $2$ trở thành $\max(0, 5-2)=3$;
• con quái vật thứ $2$ tấn công con quái vật thứ $3$, sau đòn tấn công, mức năng lượng của con quái vật thứ $3$ trở thành $\max(0, 3-3)=0$;
• con quái vật thứ $3$ tấn công con quái vật thứ $1$, sau đòn tấn công, mức năng lượng của con quái vật thứ $1$ trở thành $\max(0, 2-0)=2$;
• Nene sử dụng phép thuật Attack Your Neighbour lần thứ hai;
• con quái vật thứ $1$ tấn công con quái vật thứ $2$, sau đòn tấn công, mức năng lượng của con quái vật thứ $2$ trở thành $\max(0, 3-2)=1$;
• con quái vật thứ $2$ tấn công con quái vật thứ $3$, sau đòn tấn công, mức năng lượng của con quái vật thứ $3$ trở thành $\max(0, 0-1)=0$;
• con quái vật thứ $3$ tấn công con quái vật thứ $1$, sau đòn tấn công, mức năng lượng của con quái vật thứ $1$ trở thành $\max(0, 2-0)=2$;
• Nene sử dụng phép thuật Attack Your Neighbour lần thứ ba;
• con quái vật thứ $1$ tấn công con quái vật thứ $2$, sau đòn tấn công, mức năng lượng của con quái vật thứ $2$ trở thành $\max(0, 1-2)=0$;
• con quái vật thứ $2$ tấn công con quái vật thứ $3$, sau đòn tấn công, mức năng lượng của con quái vật thứ $3$ trở thành $\max(0, 0-0)=0$;
• con quái vật thứ $3$ tấn công con quái vật thứ $1$, sau đòn tấn công, mức năng lượng của con quái vật thứ $1$ trở thành $\max(0, 2-0)=2$.

Sau mỗi lần sử dụng phép thuật tiếp theo, mức năng lượng của các con quái vật không thay đổi. Do đó, cuối cùng chỉ có con quái vật thứ $1$ là có mức năng lượng khác không.

Trong trường hợp thử nghiệm thứ hai, cả hai con quái vật ban đầu đều có mức năng lượng bằng không.