Annettuna on lista, jossa on n kokonaislukua x_1,x_2,\dots,x_n. Tehtäväsi on käsitellä q kyselyä muotoa "mikä luku hallitsee välin [a,b] listaa".

Luku hallitsee listaa, jos yli puolet listan luvuista on kyseistä lukua. Esimerkiksi luku 1 hallitsee listaa [1,2,1,1]. On myös mahdollista, ettei mikään luku hallitse listaa. Esimerkiksi mikään luku ei hallitse listaa [1,2,1,3].

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja q: listan koko ja kyselyiden määrä.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\dots,x_n: listan sisältö.

Seuraavat q riviä kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b. Kaikissa kyselyissä 1 \le a \le b \le n.

Tuloste

Tulosta q riviä: jokaisen kyselyn vastaus. Jos mikään luku ei hallitse listaa, tulosta -1.

Esimerkki

Syöte:

8 5
1 3 2 2 1 2 4 1
3 6
4 6
5 6
2 2
5 8

Tuloste:

2
2
-1
3
-1

Selitys:

• Ensimmäisessä kyselyssä luku 2 hallitsee listaa [2,2,1,2].
• Toisessa kyselyssä luku 2 hallitsee listaa [2,1,2].
• Kolmannessa kyselyssä mikään luku ei hallitse listaa [1,2].
• Neljännessä kyselyssä luku 3 hallitsee listaa [3].
• Viidennessä kyselyssä mikään luku ei hallitse listaa [1,2,4,1].

Osatehtävä 1 (10 pistettä)

• 1 \le n, q \le 100
• 1 \le x_i \le 100

Osatehtävä 2 (20 pistettä)

• 1 \le n, q \le 10^5
• 1 \le x_i \le 10

Osatehtävä 3 (30 pistettä)

• 1 \le n, q \le 10^5
• 1 \le x_i \le 10^9

Osatehtävä 4 (40 pistettä)

• 1 \le n, q \le 2 \cdot 10^5
• 1 \le x_i \le 10^9