Есть $$$n$$$ аэропортов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. У каждого аэропорта есть свой класс обслуживания, для $$$i$$$-го аэропорта это некоторое целое число $$$a_i$$$.

Авиакомпания «Беда» осуществляет авиаперелёты с соблюдением особых условий, необходимых для поддержания высокого качества обслуживания. Так, из аэропорта $$$x$$$ существует перелёт только в следующие аэропорты:

• В аэропорт $$$y$$$, такой что $$$y \gt x$$$ и $$$a_y \gt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$x \lt z \lt y$$$ и $$$a_z \gt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \gt x$$$ и $$$a_y \lt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$x \lt z \lt y$$$ и $$$a_z \lt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \lt x$$$ и $$$a_y \gt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$y \lt z \lt x$$$ и $$$a_z \gt a_x$$$.
• В аэропорт $$$y$$$, такой что $$$y \lt x$$$ и $$$a_y \lt a_x$$$, и не существует такого аэропорта $$$z$$$, что $$$y \lt z \lt x$$$ и $$$a_z \lt a_x$$$.

Вас интересуют $$$q$$$ запросов $$$l_i, r_i$$$ таких, что $$$1 \le l_i \le r_i \le n$$$ на покупку абонемента, позволяющего не платить за перелёт, если номера обоих аэропортов находятся в промежутке от $$$l_i$$$ до $$$r_i$$$ включительно. Выгода такого абонемента определяется как количество различных групп аэропортов с номерами в промежутке от $$$l_i$$$ до $$$r_i$$$ включительно, внутри которых можно бесплатно перемещаться. Два аэропорта $$$x$$$ и $$$y$$$ находятся в одной группе, если существует бесплатный маршрут как из $$$x$$$ в $$$y$$$, так и из $$$y$$$ в $$$x$$$. Для каждого запроса требуется определить выгоду абонемента.