CC BY-NC 2.5 by Randall Munroe on xkcd.com After winning the BAPC, you decided to host a celebratory dinner in your living room. For the main course, you prepared a huge circular table with room for $$$n$$$ people to sit at. Every now and then, one person would like a condiment currently in use by another guest. To get the condiment, the person now in possession of the condiment will hand it over along a chain of people until it reaches the destination.
The $$$n$$$ guests are sitting in $$$n$$$ chairs at equidistant positions around the round table, and the guests are labeled in counterclockwise order from $$$1$$$ to $$$n$$$. It is rude to interrupt people eating, so the only way to hand something over, is by reaching behind the chairs.
For each chair, you are given the wingspan of the person sitting there, which is measured in "how many chairs can one of their arms reach behind to pass something on".
Condiments are passed around very often. Since you and your guests are algorithm enjoyers, of course, these condiment handovers should be done as efficiently as possible.
Answer $$$q$$$ queries of the type "What is the minimum number of handovers needed to hand over a condiment from person $$$u$$$ to person $$$v$$$?" Some condiment is first in possession of person $$$u$$$, and through a series of handovers must be handed to person $$$v$$$.
Person $$$x$$$ can hand over the condiment to person $$$y$$$, if the sum of their wingspans is large enough to bridge the number of chairs. More formally, if their wingspans are $$$w_x$$$ and $$$w_y$$$, the handover can happen if $$$ \min(|x-y|, n - |x-y|) \leq w_x + w_y$$$.
The input consists of:
- One line with two integers $$$n$$$ and $$$q$$$ ($$$3\leq n\leq {2 \cdot 10^5}, 1 \leq q \leq {2 \cdot 10^5}$$$), the number of chairs at the table and the number of handing over queries.
- One line with $$$n$$$ integers $$$w_1,\dots,w_n$$$ ($$$1 \leq w_i \leq n$$$ for each $$$i$$$), the wingspan of the person sitting at the $$$i$$$th chair.
- $$$q$$$ lines, each containing two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n, u \neq v$$$), describing a query of handing over a condiment from person $$$u$$$ to person $$$v$$$.
For each query, output the minimum number of handovers.
6 5 1 1 2 1 1 1 1 5 4 1 1 3 2 5 3 6
1 2 1 2 1
3 1 2 3 2 2 1
1
10 4 1 1 1 1 1 1 1 1 1 1 1 6 5 2 2 7 9 1
3 2 3 1
13 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 6
2
