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

امین از تجربه‌ی کوه‌نوردی قبلی یک نقشه به‌دست آورده است. در نقشه‌ی او $n$ کوه، کنار هم و در یک ردیف قرار داشتند به طوری که ارتفاع هیچ دو کوه مجاوری یک‌سان نبود. او به یک زیردنباله (نه لزوماً متوالی) از کوه‌ها، یک رشته‌کوه می‌گوید اگر هر کوه (به جز دو کوه اول و آخر) از هر دو کوه مجاورش، یا کوتاه‌تر باشد یا بلندتر.

حال از شما $q$ سوال مختلف پرسیده می‌شود. در هر سوال یک بازه‌ی $l$ و $r$ داده می‌شود و از شما می‌پرسیم بلندترین زیردنباله‌ای که رشته‌کوه باشد در بازه‌ی $l$ تا $r$ چقدر است؟

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $n$ که نشان دهنده‌ی تعداد کوه‌هاست، داده می‌شود. $$1 \leq n \leq 100 , 000$$

در سطر دوم ورودی، $n$ عدد صحیح و نامنفی $a_1, a_2, \dots, a_n,$ داده می‌شود که با فاصله از هم جدا شده‌اند و عدد $i$ام ارتفاع کوه $i$ام را نشان می‌دهد. $$0 \leq a_i \leq 10^9$$

در سطر سوم ورودی، عدد صحیح و مثبت $q$ داده می‌شود که نشان دهنده‌ی تعداد سوالات است. $$1 \leq q \leq 100 , 000$$

در $q$ سطر بعدی، در هر سطر دو عدد صحیح $l$ و $r$ که با یک فاصله از هم جدا شده‌اند داده می‌شود و بازه‌ی مورد سوال را نشان می‌دهد.

خروجی

برای هر سوال، طول بزرگ‌ترین زیردنباله‌ از کوه‌ها که تشکیل رشته‌کوه می‌دهند را چاپ کنید.

زیرمسئله‌ها

مثال‌ها

ورودی نمونه ۱

5
1 4 6 3 5
3
1 5
2 4
1 3

خروجی نمونه ۱

4
3
2

• در بازه‌ی ۱ تا ۵ یعنی کل اعداد و بزرگ‌ترین رشته‌کوه از حذف کوه دوم بدست می‌آید.
• در بازه‌ی ۲ تا ۴ همه‌ی کوه‌ها رشته‌کوه هستند.
• در بازه‌ی ۱ تا ۳ یک رشته کوه به اندازه‌ی دو از حذف کوه دوم بدست می‌آید.