+ محدودیت زمان: ۱ ثانیه
+ **محدودیت حافظه: ۶۴ مگابایت**
----------------
تابع $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
```
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.
