지배하는 택배 회사

바이트아사르는 컴퓨터 게임을 파는 BAJ 사에서 일한다. BAJ 사는 여러 택배 회사와 계약을 맺고, 팔린 게임을 고객에게 배송한다. 바이트아사르는 이 계약이 공정하게 지켜지는지 점검하는 중이다. 그의 손에는 발송된 소포를 순서대로 적은 기록이 있고, 소포마다 배송을 맡은 택배 회사의 번호가 함께 적혀 있다.

어떤 기간에 발송된 소포 가운데 절반을 넘는 수를 한 택배 회사가 배송했다면, 그 회사가 그 기간을 지배했다고 한다. 바이트아사르는 주어진 기간마다 그 기간을 지배한 택배 회사가 있는지, 있다면 어느 회사인지 알고 싶다.

각 기간을 지배한 택배 회사를 구하거나 그런 회사가 없음을 판정하는 프로그램을 작성하시오.

첫째 줄에 BAJ 사가 발송한 소포의 개수 $n$과 지배 여부를 판정할 기간의 개수 $m$이 공백 하나를 사이에 두고 주어진다 ($1 \le n, m \le 500\,000$). 택배 회사에는 $1$번부터 최대 $n$번까지 번호가 매겨져 있다.

둘째 줄에 $n$개의 정수 $p_1, p_2, \dots, p_n$이 공백 하나씩을 사이에 두고 주어진다 ($1 \le p_i \le n$). $p_i$는 발송 순서로 $i$번째인 소포를 배송한 택배 회사의 번호이다.

이어지는 $m$개의 줄에 기간이 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $a$와 $b$가 공백 하나를 사이에 두고 주어진다 ($1 \le a \le b \le n$). 이는 $a$번째 소포부터 $b$번째 소포까지, 양 끝을 포함한 기간을 지배한 택배 회사를 구하라는 뜻이다.

주어진 기간마다 한 줄씩, 모두 $m$개의 줄을 출력한다. 각 줄에는 그 기간을 지배한 택배 회사의 번호를 출력하고, 그런 회사가 없으면 $0$을 출력한다.