+ محدودیت زمان: ۱ ثانیه + **محدودیت حافظه: ۶۴ مگابایت** ---------------- تابع $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 ```