Dịch Vòng Tốt

Cho hoán vị $p_1,p_2,\dots ,p_N$ của $1,2,\dots ,N$. Định nghĩa:

• $$f(p)=\sum _{i=1}^N\frac{|p_i-i|}{2}$$

Một hoán vị được gọi là tốt nếu có thể biến đổi nó thành hoán vị đơn vị bằng tối đa $f(p)$ phép hoán đổi hai phần tử liền kề.

Cho một hoán vị, xác định những phép dịch vòng phải nào tạo ra hoán vị tốt. Phép dịch vòng phải $s$ bước biến $[p_1,\dots ,p_N]$ thành $[p_{N-s+1},\dots ,p_N,p_1,\dots ,p_{N-s}]$.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le {10}^5$)
• Với mỗi bộ test:
  • Dòng 1: Số nguyên $N$ ($1\le N\le 2\times {10}^5$)
  • Dòng 2: $N$ số nguyên $p_1,\dots ,p_N$

Tổng $N$ trên tất cả bộ test không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi bộ test:

• Dòng 1: Số nguyên $k$ — số phép dịch vòng tốt
• Dòng 2: $k$ số nguyên $s$ ($0\le s<N$) theo thứ tự tăng dần

Ràng buộc

• $1\le N\le 2\times {10}^5$
• $\sum N\le {10}^6$

Ví dụ

Ghi chú

• Test 2: $N\le 10$
• Test 3-5: $T\le 10$, $N\le 2000$
• Test 6-11: Không ràng buộc bổ sung