Problem H
Farming Mars
It has been ten years since the miserable day that you won a one-way ticket to Mars on a game show. Your colony’s attempt at terraforming Mars has faced nothing but hardship during that time. The latest disaster: a complete failure of the potato crop. You will have to start planting potatoes again from scratch. Your colony has prepared an $n$-acre strip of arable land on which you will attempt to plant new potatoes.
Your scientists have developed bioengineered potatoes that can withstand the harsh Martian climate and almost complete lack of atmosphere. Unfortunately, these potatoes have extreme sensitivity to pH: they will only thrive if the pH of the soil is exactly right, down to six decimal digits. Your bioengineers can create new potato varieties with any specific allowable pH value, but doing so is only economical if you can then plant a large patch of the variety on a continuous interval $[l,r]$ of the $n$-acre strip. Given a list of pH values measured on each acre of the strip, and a list of potential subintervals $[l,r]$ where you are considering planting potatoes, compute whether a strict majority $\lfloor (r-l+1)/2\rfloor + 1$ of the acres within the interval all share the exact same pH value (otherwise it is not worth trying to plant potatoes there). Note that these acres with equal pH value do not need to be contiguous, so long as they all lie within the interval $[l,r]$.
Input
The first line of input contains two space-separated integers $n$ and $m$ $(1 \leq n,m \leq 10\, 000)$, the size of the strip of land and the number of queries, respectively. The next $n$ lines contain a single real number: the $i$th such number is the pH of the $i$th acre along the strip. Each pH value lies between $0.000000$ and $14.000000$, inclusive, and contains exactly six decimal digits after the decimal point. Then follows $m$ lines containing two space-separated integers each: the bounds $l_ j$ and $r_ j$ of the $j$th query $(1 \leq l_ j \leq r_ j \leq n)$.
Output
Print $m$ lines of output, one for each query. On line $j$, print usable if a strict majority of the land between acres $l_ j$ and $r_ j$ (inclusive) all share the exact same pH value, and unusable otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 4 7.000000 8.314634 7.000001 7.000000 2.581236 7.000000 2.581236 7.000000 1 8 1 3 4 8 5 7 |
unusable unusable usable usable |
