#889. PHOTO - Bức ảnh đẹp

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho n viên bi xếp thành hàng ngang, viên thứ i có màu a_i\ (1≤a_i≤C) . Một bức ảnh đẹp là một đoạn con liên tiếp các viên bi sao cho trong đó có nhiều hơn một nửa trong số đó có cùng màu.

Cho Q truy vấn, mỗi truy vấn cho hai số nguyên i,j\ (1≤i≤j≤n) .

Yêu cầu: Với mỗi truy vấn, kiểm tra xem bức ảnh chụp đoạn [i,j] có đẹp không? Màu nào xuất hiện nhiều hơn một nửa trong số các viên bi trong đoạn đó.

Dữ liệu:

  • Dòng đầu chứa hai số n,C\ (3≤n≤3\times 10^5,1≤C≤10^4) ;
  • Dòng thứ hai chứa n số a_1,a_2,…,a_n\ (1≤a_i≤C) ;
  • Dòng thứ ba chứa số Q\ (1≤Q≤10^4) ;
  • Q dòng sau, mỗi dòng chứa thông tin một truy vấn.

Kết quả:

  • Ứng với mỗi truy vấn, in kết quả trên một dòng. Nếu bức ảnh là đẹp thì ghi 1\ x với x là màu xuất hiện quá một nửa trong số các viên bi. Ngược lại, in 0 .

Ví dụ:

Dữ liệu:

10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

Kết quả:

0
1 1
0
1 1
0
1 2
0 
1 3

Ràng buộc:

  • 30\% số test tương ứng với 30\% số điểm có n,Q≤1000 ;
  • 30\% số test tương ứng với 30\% số điểm có n≤300000,Q≤10000,1≤C≤30 ;
  • 40\% số test tương ứng với 40\% số điểm không có ràng buộc gì thêm.