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

---

تابع $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<j)$

به شما $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