4 năm sau ….
“Mình đã làm sai nhiều thứ, nhưng yêu cậu thì tuyệt đối là điều đúng đắn nhất mình từng quyết định”. Có mấy ai khi yêu nhau ở tuổi 17 tươi đẹp nhưng cũng đầy bồng bột, có thể trải qua 4 năm sóng gió ? Có cuộc tình nào kì diệu và mạnh mẽ để vượt đủ 4 năm đầy bão giông ? Và quan trọng hơn, có mấy ai đủ tin tưởng nhau để cùng nắm tay qua từng ấy thử thách ?
Chính vì lẽ đó mà cuộc tình Ami và LN mới kì diệu đến thế. Ami tin tưởng LN, cậu mời LN đến cạnh mình để trải qua một ngày cực kì trọng đại cùng mình. Nhưng Ami và LN ở rất xa nhau, và chi phí để di chuyển không phải là nhỏ. Vì thế, Ami phải lựa chọn phương tiện cực kì đắn đo. Hiện tại, Ami đang đứng trước quầy bán vé điện tử, và cậu có thông tin của người mua hàng. Mỗi người được đánh số thứ tự từ 1 đến n và sẽ mua loại vé ai. Ami sẽ mua chiếc vé được nhiều người mua nhất. Nhưng, mọi chuyện đâu đơn giản như vậy, Ami luôn chọn những con số nhiều ý nghĩa, như 5 , 17, 20, …, vì vậy, Ami sẽ chỉ quan tâm đến những người mang số thứ tự từ L đến R (L <= R). Các bạn hãy tính toán xem, số lượng người nhiều nhất trong một đoạn nhất định đã mua một loại vé là bao nhiêu.
Dữ liệu vào
Dòng đầu tiên là 1 số nguyên dương n - số người mua vé (n <= 5000).
Dòng tiếp theo gồm n số nguyên dương a1, a2, … , an (an <= 106) là loại vé mà người i đã mua.
Dòng thứ ba là 1 số nguyên dương q - số đoạn thứ tự mà Ami quan tâm. (q <= 5000).
Q dòng cuối cùng, mỗi dòng chứa 2 số nguyên dương L và R (L <= R <= N) là một đoạn thứ tự Ami muốn lấy thông tin.
Dữ liệu ra
Q dòng, mỗi dòng một số nguyên dương - số lượng người nhiều nhất đã mua một loại vé trong một đoạn tương ứng.
Input
5
1 1 2 2 3
3
1 4
1 3
4 5
Output
2
2
1
Giải thích
Trong đoạn từ 1 đến 4, có 2 người mua vé loại 1, 2 người mua vé loại 2, do đó kết quả là 2.
Trong đoạn từ 1 đến 3, có 2 người mua vé loại 1, 1 người mua vé loại 2, do đó kết quả là 2.
Trong đoạn từ 4 đến 5, có 1 người mua vé loại 3, 1 người mua vé loại 2, do đó kết quả là 1.