Nhịp Đập Thị Trấn
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Thị trấn có N cửa hàng xếp thành dãy, cửa hàng thứ i có loại hàng hóa a_i. Có Q câu hỏi, mỗi câu hỏi cho l, r, hỏi tần suất xuất hiện nhiều nhất (mode frequency) của bất kỳ loại hàng nào trong đoạn [l, r].
Nói cách khác, tìm max(freq(x)) với x xuất hiện trong a[l..r].
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 100000). Q dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ N).
Dữ liệu ra
Với mỗi truy vấn, in ra tần suất xuất hiện lớn nhất trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 7 3\n1 2 1 3 2 1 3\n1 7\n1 3\n4 7 | 3\n2\n2 |
Giới hạn
- 1 ≤ N, Q ≤ 100000
- 1 ≤ a_i ≤ 100000
- 1 ≤ l ≤ r ≤ N
Community Discussion