Floppy

Roxette는 오래된 기술 애호가로, $N$개의 서로 다른 정수로 이루어진 배열 $v_0, v_1, v_2, \dots, v_{N-1}$을 발견했다. 흥미를 느낀 그녀는 이 배열을 플로피 디스크에 저장하고 싶어 한다. 하지만 디스크 여유 공간이 부족해서 배열 전체를 저장할 수 없다. 대신 아래 형태의 어떤 질의에도 답할 수 있는 비트 배열을 저장하려고 한다.

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

즉, 질의는 주어진 부분 배열에서 최댓값이 있는 인덱스를 돌려준다.

Roxette는 두 번 도움을 요청한다. 먼저 배열을 주면, 디스크에 저장할 비트 열을 알려 준다. 다음으로 그녀가 어떤 질의의 답이 필요할 때, 앞서 알려 준 비트 열과 질의를 함께 주면, 각 질의의 올바른 답을 알려 준다.

• 모든 $0 \le i \le N - 1$에 대해 $-10^9 \le v_i \le 10^9$
• $1 \le L \le 200\,000$