Service Lane

Service lane has varying widths. For each query (entry i, exit j), find minimum width in segment [i,j]. Output the largest vehicle type that can pass: 1=bike, 2=car, 3=truck. Example: widths=[2,3,1,2,3,2,3,3], query [0,3] → min width in [2,3,1,2] is 1 → Output: 1 (only bike can pass)

Input

First line: n t (space-separated). Second line: n space-separated integers (widths). Next t lines: i j (space-separated, entry and exit indices).

Output

For each query, output the maximum vehicle type (1, 2, or 3) that can pass.

Sample

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

Expected

1
2
3
2
1