Problem
Baru-baru ini berada di dalam hutan, Vasya memutuskan untuk membina kereta kabel di atas pokok. Dia mahu jalan itu sepanjang mungkin, tetapi dia tidak ingat dengan baik ketinggian pokok di dalam hutan. Nasib baik, dia yakin bahawa dia mengingati ketinggian semua pokok dengan betul, kecuali mungkin salah satu daripadanya.
Diketahui bahawa hutan tersebut terdiri daripada n pokok yang disusun sebaris dan dinomborkan dari kiri ke kanan dengan nombor dari 1 hingga n. Ketinggian pokok ke-i, menurut Vasya, ialah hi. Sebuah kereta kabel dengan panjang k mesti diletakkan di atas pokok k (1 <= k <= n) i1, i2, . . . , ik (i1 < i2 < . . . < ik), seperti bahawa ketinggian mereka bertambah, iaitu, hi1 < hi2 < . . . < hik.
Petya juga berada di dalam hutan, dan dia telah meneka dengan tepat di mana kesilapan Vasya. Tekaan ke-inya diberikan oleh nombor ai dan bi , bermakna, pada pendapat Petya, ketinggian pokok
dengan nombor ai sebenarnya sama dengan bi . Sila ambil perhatian bahawa andaian Petya adalah bebas antara satu sama lain.
Tugas anda adalah untuk mencari, bagi setiap tekaan Petya, panjang maksimum kereta kabel yang boleh dibina berdasarkan pokok ini.
Ambil perhatian bahawa dalam rangka masalah ini, Vasya menganggap bilangan pokok penyokong di dalamnya sebagai panjang jalan.
Format data input
Baris pertama input mengandungi dua nombor n dan m (1 <= n, m <= 400 000) — bilangan pokok di dalam hutan dan bilangan tekaan Petya, masing-masing.
Baris seterusnya mengandungi n integer hi (1 <= hi <= 109 ) — ketinggian pokok mengikut cadangan Vasya.
Setiap baris m seterusnya mengandungi dua integer ai dan bi (1 <= ai <= n, 1 <= bi <= 109 ).
Format output
Untuk setiap tekaan Petya, cetak pada baris berasingan satu nombor — panjang maksimum kereta kabel.
|
Masukkan |
Output |
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 |
Nota
Mari kita pertimbangkan contoh pertama. Andaian pertama Petya bertepatan dengan andaian Vasya.
Mengikut andaian kedua beliau, ketinggian pokok adalah (4, 2, 3, 4), yang ketiga (1, 2, 3, 3), dan mengikut andaian keempat — (1, 2, 3, 5).