- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
تابع \(f(i , j)\) روی آرایهی \(a\) به طول \(n\) به این شکل تعریف میشود:
- \(f(i , i) = a_{i}\)
- \(f(i , j) = max( f(i+1 , j) , f(i , j-1) , min( a_{i} , a_{i+1} , ... , a_{j} ) \times (j-i+1) ) (i
به شما \(Q\) جفت عدد داده میشود.
هر جفت دارای دو عدد \(l_{i}\) و \(r_{i}\) است.
مقدار زیر را خروجی دهید:
\[max( f(l_{1} , r_{1}) , f(l_{2} , r_{2}) , ... , f(l_{Q} , r_{Q}) )\]
ورودی
در خط اول دو عدد \(n\) و \(Q\) داده میشود.
در خط بعدی \(n\) عدد \(a_{1}\) تا \(a_{n}\) داده میشود.
در \(Q\) خط بعدی\(l_{i}\) و \(r_{i}\) به شما داده میشود.
\[1 \le Q,n \le 1\ 000\ 000\]
\[1 \le a_{i} \le 1\ 000\ 000\ 000\]
\[1 \le l_{i} \le r_{i} \le n\]
تضمین میشود تمام اعداد آرایه \(a\) متمایزند.
خروجی
مقدار خواسته شده را خروجی دهید.
مثال
ورودی نمونه ۱
5 2
1 4 3 5 2
1 3
3 5
خروجی نمونه ۱
6
ارسال پاسخ برای این سؤال