Problem
Yakın zamanda ormanda bulunan Vasya, ağaçların üzerine bir teleferik yapmaya karar verdi. Yolun olabildiğince uzun olmasını istiyor ama ormandaki ağaçların yüksekliklerini pek iyi hatırlamıyor. Neyse ki biri hariç tüm ağaçların yüksekliğini doğru hatırladığından emin.
Ormanın arka arkaya dizilmiş ve soldan sağa 1'den n'ye kadar numaralandırılmış n ağaçtan oluştuğu bilinmektedir. Vasya'ya göre i'inci ağacın yüksekliği hi'dir. k uzunluğundaki bir teleferik, k (1 <= k <= n) ağaç üzerinde durmalıdır i1, i2, . . . , ik (i1 < i2 < . . . < ik), böyle boylarının arttığını, yani hi1 < hi2 < . . . < hik.
Petya da ormandaydı ve Vasya'nın tam olarak nerede yanıldığına dair q tahmini var. i'nci tahmini ai ve bi sayıları tarafından verilir, yani Petya'ya göre ağacın yüksekliği
ai sayısı aslında bi değerine eşittir. Lütfen Petya'nın varsayımlarının birbirinden bağımsız olduğunu unutmayın.
Göreviniz, Petya'nın her tahmininde bu ağaçlara göre inşa edilebilecek teleferiğin maksimum uzunluğunu bulmak.
Dikkat edin, bu problem çerçevesinde Vasya, içindeki destekleyici ağaçların sayısını yolun uzunluğu olarak kabul eder.
Giriş verisi biçimi
Girişin ilk satırı n ve m olmak üzere iki sayı içerir (1 <= n, m <400 000) — sırasıyla ormandaki ağaç sayısı ve Petya'nın tahmin sayısı.
Sonraki satır n tamsayı içerir hi (1 <= hi <= 109 ) — Vasya'nın önerisine göre ağaçların yüksekliği.
Sonraki m satırın her biri iki tam sayı ai ve bi içerir (1 <= ai <= n, 1 <= bi <= 109 ).
Çıktı biçimi
Petya'nın her tahmini için ayrı bir satıra bir sayı yazdırın — teleferiğin maksimum uzunluğu.
|
Gir |
Çıktı |
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 |
Not
İlk örneği ele alalım. Petya'nın ilk varsayımı Vasya'nınkiyle örtüşüyor.
İkinci varsayımına göre ağaçların boyları (4, 2, 3, 4), üçüncüsü (1, 2, 3, 3) ve dördüncü varsayımına göre ise — (1, 2, 3, 5).