Snow Boots

Winter has arrived at the farm, and with it snow. The path from the farmhouse to the barn is made of $N$ tiles, numbered $1$ through $N$ starting at the house, and tile $i$ is covered in $f_i$ feet of snow.

The farmer keeps $B$ pairs of boots in the cellar, numbered $1$ through $B$. Some pairs are sturdier than others and some are lighter than others. Pair $i$ lets the farmer step in snow at most $s_i$ feet deep, and lets him move at most $d_i$ tiles forward in one step.

The farmer starts on tile $1$ and has to reach tile $N$ to wake the cows. The farmhouse roof covers tile $1$ and the barn roof covers tile $N$, so neither tile has snow on it.

One step moves the farmer forward by at least $1$ and at most $d_i$ tiles, and the tile he lands on must be covered by at most $s_i$ feet of snow. The snow on the tiles he passes over does not matter. For each pair of boots, decide whether the farmer can get from tile $1$ to tile $N$.

The first line contains two space separated integers $N$ and $B$ ($1 \leq N, B \leq 10^5$).

The second line contains $N$ space separated integers. The $i$th integer is $f_i$, the depth of the snow on tile $i$ ($0 \leq f_i \leq 10^9$). It is guaranteed that $f_1 = f_N = 0$.

Each of the next $B$ lines contains two space separated integers. The first integer on line $i+2$ is $s_i$, the maximum depth of snow that pair $i$ can step in. The second integer is $d_i$, the maximum number of tiles pair $i$ can move forward in one step ($0 \leq s_i \leq 10^9$, $1 \leq d_i \leq N-1$).

Print $B$ lines. Line $i$ contains $1$ if the farmer can walk from tile $1$ to tile $N$ wearing pair $i$, and $0$ otherwise.