Độ khó: Trung bình (2/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

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Nguồn: Đề thi HSG Tin học – Bài 3 (7,0 điểm).

Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò tìm số. Hai bạn lần lượt mỗi người viết một số nguyên dương lên bảng, Nam viết số thứ nhất, Bình viết số thứ hai, rồi đến lượt Nam viết số thứ ba,… Cứ tiếp tục như vậy hai bạn viết được một dãy gồm ~n~ số ~a_1, a_2, \ldots, a_n~. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẵn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho đoạn đó có nhiều số nhất và số lượng số chẵn trong đoạn bằng số lượng số lẻ trong đoạn đó.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai ghi dãy ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 1000,\ i = 1..n)~.

Kết quả

• Một số nguyên duy nhất là số lượng số của dãy con tìm được. Nếu không có đoạn nào thoả mãn (ví dụ ~n = 1~), in ra ~0~.

Giới hạn

• Có 60% số test tương ứng 60% số điểm có giá trị ~1 \le n \le 10^2~.
• Có 20% số test tương ứng 20% số điểm có giá trị ~10^2 \lt n \le 10^3~.
• Có 20% số test tương ứng 20% số điểm có giá trị ~10^3 \lt n \le 10^6~.

Sample Input 1

8
3 4 2 6 5 8 7 2

Sample Output 1

4

Giải thích

Dãy ~3, 4, 2, 6, 5, 8, 7, 2~. Đoạn ~6, 5, 8, 7~ (vị trí 4 → 7) có 2 số chẵn (~6, 8~) và 2 số lẻ (~5, 7~) nên thoả mãn, dài 4. Đoạn ~5, 8, 7, 2~ cũng thoả và dài 4. Không có đoạn dài 6 hay 8 nào thoả (ví dụ ~3, 4, 2, 6, 5, 8~ có tới 4 số chẵn, 2 số lẻ), nên đáp án là ~4~.