Problem
Gần đây đã ở trong rừng, Vasya quyết định xây dựng một chiếc cáp treo trên cây. Anh ấy muốn con đường càng dài càng tốt, nhưng anh ấy không nhớ rõ độ cao của những cái cây trong rừng. May mắn thay, anh ấy chắc chắn rằng mình nhớ chính xác chiều cao của tất cả các cây, có lẽ chỉ trừ một trong số chúng.
Biết khu rừng gồm n cây được xếp thành một hàng và được đánh số thứ tự từ trái sang phải với các số từ 1 đến n. Theo Vasya, chiều cao của cây thứ i là hi. Cáp treo dài k phải nằm trên k (1 <= k <= n) cây i1, i2, . . . , ik (i1 < i2 < . . < ik), chẳng hạn rằng chiều cao của họ tăng lên, nghĩa là hi1 < hi2 < . . . < hik.
Petya cũng ở trong rừng, và anh ấy đã đoán được chính xác Vasya đã sai ở đâu. Dự đoán thứ i của anh ấy được đưa ra bởi các số ai và bi , nghĩa là, theo ý kiến của Petya, chiều cao của cái cây
với số ai thực sự bằng bi . Xin lưu ý rằng các giả định của Petya là độc lập với nhau.
Nhiệm vụ của bạn là tìm, đối với mỗi dự đoán của Petya, chiều dài tối đa của cáp treo có thể được xây dựng dựa trên những cái cây này.
Lưu ý rằng trong khuôn khổ của bài toán này, Vasya coi số lượng cây chống đỡ trong đó là chiều dài của con đường.
Định dạng dữ liệu đầu vào
Dòng đầu tiên chứa hai số n và m (1 <= n, m <= 400 000) — số cây trong rừng và số lần Petya đoán tương ứng.
Dòng tiếp theo chứa n số nguyên hi (1 <= hi <= 109 ) — chiều cao của cây theo gợi ý của Vasya.
Mỗi m dòng tiếp theo chứa 2 số nguyên ai và bi (1 <= ai <= n, 1 <= bi <= 109 ).
Định dạng đầu ra
Đối với mỗi dự đoán của Petya, hãy in trên một dòng riêng biệt một số — chiều dài tối đa của cáp treo.
|
Nhập |
Đầu ra |
4 4
1 2 3 4
1 1
14
4 3
4 5 |
4
3
3
4 |
4 2
1 3 2 6
3 5
24 |
4
3 |
Lưu ý
Hãy xem xét ví dụ đầu tiên. Giả định đầu tiên của Petya trùng khớp với giả định của Vasya.
Theo giả định thứ hai của anh ấy, chiều cao của các cây là (4, 2, 3, 4), cây thứ ba (1, 2, 3, 3) và theo giả định thứ tư — (1, 2, 3, 5).