- محدودیت زمان: ۴ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آی مجری که به فکر بچه‌ها است، تصمیم گرفته است که گابی را به مسابقات شنا بفرستد تا او با شنا مشغول شده و لاغر شود اما مشکلی که وجود دارد این است که گابی از آب می‌ترسد. آی مجری فرایندی را برای ریختن ترس گابی از آب طراحی کرده است که به آن فرایند ترس‌ریزی می‌گویند و روی دنباله‌ی $a$ به این صورت اجرا می‌شود:
او ابتدا تعدادی استخر را پر از آب می‌کند که عمق استخر $i$، $a_i$ می‌باشد. سپس با کمک بقیه گابی را به استخر شماره‌ی ۱ می‌اندازد و گابی که نمی‌تواند از آن بیرون بیاید، در آن می‌ماند و ترسش از استخری با عمق $a_1$ و کمتر می‌ریزد. سپس آی مجری گابی را از استخر شماره‌ی ۱ بیرون می‌آورد و از بین اعداد ۲ تا $n$ کوچکترین عدد (مانند $j$) را انتخاب می‌کند که $a_1<a_j$ و گابی را در درون استخر $j$ می‌اندازد تا ترسش از عمق کمتر از آن هم بریزد. سپس او همین کار را ادامه می‌دهد و استخر دیگری با شماره‌ی $k$ انتخاب می‌کند که $k>j$ و $a_k>a_j$. سپس همینکار را ادامه می‌دهد(یعنی جلو می‌رود تا استخری با عمق بیشتر از قبلی را پیدا کند و گابی را درون آن بیاندازد) تا به پایان دنباله برسد. حالا اگر در این فرایند ترس‌ریزی آی مجری گابی را $d$ بار درون آب بیاندازد، مقدار خوبی این فرایند $d$ می‌شود.
به تازگی نزدیک خانه‌ی آی مجری مغازه‌ای باز شده است که توانایی ساختن استخر‌هایی با $n$ عمق متفاوت $b_1$، $b_2$، $b_3$ ... $b_n$ را دارد. حالا آی مجری به این صورت می‌خواهد به این مغازه سفارش دهد که برایش یک فرایند ترس‌ریزی بسازد:
او به مغازه دار چهار عدد $l_1$، $r_1$، $l_2$ و $r_2$ را می‌دهد و آقای مغازه دار یک فرایند ترس‌ریزی با استخر‌هایی با عمق‌های زیر برای او می‌سازد:
$$b_{l_1}, b_{l_1+1} , b_{l_1+2} , ... , b_{r_1} , b_{l_2}, b_{l_2+1} , b_{l_2+2} , ... , b_{r_2} $$
آی مجری بین $q$ درخواست که می‌تواند به مغازه‌دار بدهد تا برایش فرایند ترس‌ریزی درست کند مانده است که کدام را انتخاب کند. برای همین او از شما می‌خواهد مقدار خوبی هر فرایند را خروجی دهید تا او بتواند با دست بازتری انتخاب کند.
ورودی
در سطر اول ورودی دو عدد $n$ و $q$ می‌آید که عدد اول نمایانگر تعداد عمق‌های متفاوتی است که مغازه‌دار می‌تواند بسازد و عدد دوم نمایانگر تعداد در‌خواست‌هایی است که آی مجری می‌تواند به مغازه‌دار بدهد. سپس در سطر دوم $n$ عدد می‌آید که عدد $i$، $b_i$ می‌باشد. بعد از آن ورودی $q$ سطر دارد که در سطر $i$، درخواست $i$ ام به صورت چهار عدد $l_1$، $r_1$، $l_2$ و $r_2$ می‌آید. $$ 1 \le n,q \le 500\ 000 $$ $$ 1 \le b_i \le 10^9 $$
خروجی
خروجی شامل $q$ سطر است که سطر $i$، شامل مقدار خوبی فرایند ترس‌ریزی است که مغازه‌دار با استفاده از درخواست $i$ ام آی مجری می‌تواند بسازد.
مثال
ورودی نمونه ۱
3 2
1 5 7
1 2 2 3
1 2 3 3
خروجی نمونه ۱
3
3
فرایند ساخته شده با استفاده از درخواست اول: 1،5،5،7
فرایند ساخته شده با استفاده از درخواست دوم: 1،5،7
ورودی نمونه ۲
3 2
5 1 7
1 3 1 2
1 1 3 3
خروجی نمونه ۲
2
2
فرایند ساخته شده با استفاده از درخواست اول: 5،1،7،5،1
فرایند ساخته شده با استفاده از درخواست دوم: 5،7
ارسال پاسخ برای این سؤال