Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^9)~. Một đoạn con ~a[i..j]~ có độ dài là ~j - i + 1~ ~(1 \le i \le j \le N)~. Đoạn con được gọi là đoạn xen kẽ nếu hai phần tử bất kỳ nào đứng cạnh nhau đều trái dấu.

Yêu cầu: Với mỗi vị trí ~i~ ~(1 \le i \le N)~ hãy tính độ dài dãy con xen kẽ dài nhất của dãy ~A~ bắt đầu ở vị trí ~i~.

Dữ liệu vào

• Dòng đầu ghi ~T~ là số lượng bộ test ~(1 \le T \le 20)~.
• Trong ~2T~ dòng tiếp theo ghi thông tin về các bộ test: dòng đầu ghi ~N~, dòng hai ghi dãy ~A~.

Kết quả

• Gồm ~T~ dòng, mỗi dòng ghi ~N~ số nguyên lần lượt là độ dài dãy con xen kẽ dài nhất tìm được tương ứng với mỗi test trong input.

Giới hạn

• Thời gian: 1.0 giây, bộ nhớ: 128 megabyte.

Subtask

• Subtask 1 (~50\%~ số điểm): ~1 \le N \le 1000~.
• Subtask 2 (~50\%~ số điểm): ~N \le 100.000~.

Sample Input 1

1
6
-5 -4 -3 1 -2 -1

Sample Output 1

1 1 3 2 1 1

Nguồn: VinhDinhCoder.