Giáo sư JOI, chuyên gia hàng đầu về lịch sử nước IOI, nhận được một cuốn nhật ký được cho là do một cư dân nước IOI thời cổ đại viết. Để nghiên cứu cuộc sống ở nước IOI thời cổ đại thông qua cuốn nhật ký này, giáo sư quyết định khảo sát các sự kiện được ghi lại trong đó.

Cuốn nhật ký ghi lại các sự kiện xảy ra trong \(N\) ngày, mỗi ngày đúng một sự kiện. Các sự kiện được chia thành nhiều loại. Loại của sự kiện vào ngày thứ \(i\) (\(1 \le i \le N\)) được biểu diễn bằng số nguyên \(X_i\). Giá trị \(X_i\) càng lớn thì sự kiện được xem là có quy mô càng lớn.

Giáo sư JOI quyết định phân tích nhật ký theo cách sau:

1. Chọn một số ngày liên tiếp trong \(N\) ngày của cuốn nhật ký làm khoảng thời gian cần phân tích.
2. Định nghĩa độ quan trọng của loại sự kiện \(t\) bằng \(t\) nhân với số sự kiện thuộc loại \(t\) trong khoảng thời gian đó.
3. Tính độ quan trọng của tất cả các loại sự kiện và lấy giá trị lớn nhất.

Giáo sư JOI giao cho bạn viết một chương trình phục vụ việc phân tích. Chương trình cần tìm được độ quan trọng lớn nhất khi được cho một khoảng thời gian cần phân tích.

Yêu cầu

Cho loại sự kiện của \(N\) ngày trong nhật ký và \(Q\) truy vấn, mỗi truy vấn chỉ định một khoảng thời gian trong nhật ký. Hãy viết chương trình tìm độ quan trọng lớn nhất của các loại sự kiện đối với từng truy vấn.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N, Q\) cách nhau bởi dấu cách, cho biết nhật ký có \(N\) ngày và có \(Q\) truy vấn.
• Dòng tiếp theo chứa \(N\) số nguyên \(X_1, \ldots, X_N\) cách nhau bởi dấu cách. \(X_i\) (\(1 \le i \le N\)) là loại sự kiện của ngày thứ \(i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le Q\)) chứa hai số nguyên \(A_j, B_j\) cách nhau bởi dấu cách, với \(1 \le A_j \le B_j \le N\). Truy vấn thứ \(j\) xét khoảng thời gian từ ngày thứ \(A_j\) đến hết ngày thứ \(B_j\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa một số nguyên là độ quan trọng lớn nhất đối với truy vấn thứ \(j\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

• \(1 \le N \le 100\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le X_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 100\), \(Q \le 100\).
• Nhóm 2 (10 điểm): \(N \le 5\,000\), \(Q \le 5\,000\).
• Nhóm 3 (25 điểm): Không tồn tại \(i, j\) với \(1 \le i,j \le Q\), \(i \ne j\) sao cho \(A_i \le A_j \le B_j \le B_i\).
• Nhóm 4 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

9
8
8
16
16

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

27
18
19
19

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15