Giá trị tối thiểu trên dữ liệu tĩnh

Bối cảnh và bài toán

Một bộ dữ liệu gồm n số được nạp một lần và không thay đổi. Có rất nhiều truy vấn hỏi giá trị nhỏ nhất trên một đoạn. Hãy lựa chọn cấu trúc phù hợp từ những công cụ đã học và giải quyết workload này.

Yêu cầu

Trả lời giá trị nhỏ nhất trên mỗi đoạn.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n số.
• q dòng tiếp theo chứa l r.

Output

In min trên từng đoạn [l,r].

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= a[i] <= 10^9
• 1 <= l <= r <= n

Chấm điểm

Ví dụ 1

Input

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Output

2
1
1
4

Giải thích. Dữ liệu không đổi; mỗi truy vấn chỉ đọc một đoạn.

Ví dụ 2

Input

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

Output

8
5
5

Giải thích. Bao gồm truy vấn một phần tử và toàn mảng.

Thông tin bài tập

Nguồn: Phỏng theo CSES – Static Range Minimum Queries.