• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

---

تابع \(f(i , j)\) روی آرایه‌ی \(a\) به طول \(n\) به این شکل تعریف می‌شود:

1. \(f(i , i) = a_{i}\)
2. \(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