Problem
واسیا که اخیراً در جنگل بوده تصمیم گرفت روی درختان تله کابین بسازد. او می خواهد جاده تا آنجا که ممکن است طولانی باشد، اما بلندی درختان جنگل را به خوبی به خاطر نمی آورد. خوشبختانه او مطمئن است که ارتفاع همه درختان را به درستی به یاد می آورد، به جز یکی از آنها.
مشخص است که جنگل شامل n درخت است که در یک ردیف قرار گرفته اند و از چپ به راست با اعداد از 1 تا n شماره گذاری شده اند. ارتفاع درخت i به گفته واسیا hi است. یک تله کابین به طول k باید روی k (1 <= k <= n) درخت i1, i2, . . . , ik (i1 < i2 < . . . < ik)، مانند که قد آنها افزایش می یابد، یعنی hi1 < hi2 < . . . &آن؛ hik.
پتیا نیز در جنگل بود، و او حدس می زند که دقیقا کجا واسیا اشتباه می کند. حدس i-ام او با اعداد ai و bi به دست می‌آید، به این معنی که به نظر پتیا، ارتفاع درخت
با عدد ai در واقع برابر با bi است. لطفاً توجه داشته باشید که مفروضات پتیا مستقل از یکدیگر هستند.
وظیفه شما این است که برای هر یک از حدس های پتیا، حداکثر طول تله کابینی را که می توان بر اساس این درختان ساخت.
پیدا کنید.
توجه داشته باشید که در چارچوب این مشکل، واسیا تعداد درختان پشتیبان در آن را طول راه می داند.
قالب داده های ورودی
خط اول ورودی شامل دو عدد n و m (1 <= n، m <= 400 000) — تعداد درختان جنگل و تعداد حدس های پتیا به ترتیب.
خط بعدی حاوی n عدد صحیح hi (1 <= hi <= 109 ) — ارتفاع درختان طبق پیشنهاد واسیا.
هر یک از خطوط m بعدی شامل دو عدد صحیح ai و bi است (1 <= ai <= n, 1 <= bi <= 109 ).
فرمت خروجی
برای هر حدس پتیا، در یک خط جداگانه یک عدد — حداکثر طول تله کابین.
<بدن>
|
وارد کنید |
خروجی |
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 |
یادداشت
بیایید مثال اول را در نظر بگیریم. اولین فرض پتیا با واسیا مطابقت دارد.
طبق فرض دوم او ارتفاع درختان (4، 2، 3، 4)، سومین (1، 2، 3، 3) و طبق فرض چهارم — (1، 2، 3، 5).