Bảo tàng Mỹ thuật JOI sắp tổ chức một triển lãm tranh. Bảo tàng sở hữu \(N\) bức tranh, được đánh số từ \(1\) đến \(N\). Bức tranh \(i\) (\(1 \le i \le N\)) có độ đẹp \(A_i\). Các bức tranh sẽ được xếp thành một hàng từ trái sang phải, nhưng thứ tự trưng bày chưa được quyết định.

Có \(M\) tạp chí sẽ đưa tin về triển lãm. Các tạp chí được đánh số từ \(1\) đến \(M\) theo thứ tự giảm dần về mức độ ảnh hưởng. Mỗi tạp chí sẽ đăng ảnh của các bức tranh trong một đoạn liên tiếp của hàng tranh. Cụ thể, tạp chí \(j\) (\(1 \le j \le M\)) sẽ đăng ảnh của các bức tranh ở vị trí \(L_j,L_j+1,\ldots,R_j\) tính từ trái sang phải. Độ hấp dẫn của bài viết trên tạp chí \(j\) là độ đẹp lớn nhất trong số các bức tranh mà tạp chí đó đăng ảnh.

JOI, giám đốc bảo tàng, muốn sắp xếp tranh để các tạp chí viết được những bài có độ hấp dẫn cao hơn, qua đó thu hút nhiều người đến triển lãm. Vì các tạp chí có ảnh hưởng lớn tiếp cận được nhiều độc giả hơn, JOI ưu tiên tăng độ hấp dẫn của bài viết trên những tạp chí đó.

Chính xác hơn, gọi \(b_j\) là độ hấp dẫn của bài viết trên tạp chí \(j\) (\(1 \le j \le M\)). JOI muốn sắp xếp tranh sao cho dãy \(b=(b_1,b_2,\ldots,b_M)\) lớn nhất theo thứ tự từ điển. Với hai dãy khác nhau \(b=(b_1,b_2,\ldots,b_M)\) và \(b'=(b'_1,b'_2,\ldots,b'_M)\), dãy \(b\) lớn hơn \(b'\) theo thứ tự từ điển nếu tại chỉ số \(k\) nhỏ nhất mà \(b_k \ne b'_k\), ta có \(b_k>b'_k\).

Cho thông tin về các bức tranh và các tạp chí. Hãy tính độ hấp dẫn của bài viết trên mỗi tạp chí khi các bức tranh được sắp xếp để dãy \(b\) lớn nhất theo thứ tự từ điển.

Dữ liệu vào

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

• Dòng thứ nhất chứa hai số nguyên \(N,M\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(L_j,R_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn \(M\) dòng. Dòng thứ \(j\) (\(1 \le j \le M\)) chứa \(b_j\), độ hấp dẫn của bài viết trên tạp chí \(j\). Dãy \(b=(b_1,b_2,\ldots,b_M)\) phải lớn nhất theo thứ tự từ điển.

Ràng buộc

• \(1 \le N \le 100000\).
• \(1 \le M \le 100000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N\).
• \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(19\) điểm: \(N \le 400\), \(M \le 400\).
2. \(9\) điểm: \(N \le 400\).
3. \(19\) điểm: \(A_i \le 5\) với mọi \(1 \le i \le N\).
4. \(12\) điểm: \(A_i=i\) với mọi \(1 \le i \le N\).
5. \(17\) điểm: Với mỗi \(k\) (\(1 \le k \le N\)), có nhiều nhất \(5\) chỉ số \(i\) thỏa mãn \(A_i=k\).
6. \(24\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4 4
1 2 1 2
1 1
2 3
4 4
3 4

2
2
1
2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

4
4
3
2
4
1
1
3

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

6
5
5
6
5
3
6
5
5
3

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm thông báo triển khai và thông tin chấm điểm.