Floppy

Roxette, an old tech geek, came across an array $v_0, v_1, v_2, \dots, v_{N-1}$ of $N$ distinct integers. Finding it interesting, she wanted to save the array on her floppy disk. However, her disk has little free space, so she cannot save the whole array. Instead, she plans to save an array of bits that lets her answer any query of the following form:

$query(a, b) = id$, where $a \le id \le b$ and $v_{id} = \max(v_a, v_{a+1}, \dots, v_{b-1}, v_b)$

In other words, the query returns the index of the maximum value in a given sub-array.

Roxette asks for your help twice. First, she gives you the array, and you tell her which sequence of bits to save on the disk. Second, when she needs answers to some queries, she gives you the bit sequence you chose along with the queries, and you provide the correct answer to each query.

• $-10^9 \le v_i \le 10^9$ for all $0 \le i \le N - 1$
• $1 \le L \le 200\,000$