Annettuna on lista, jossa on n positiivista kokonaislukua järjestyksessä pienimmästä suurimpaan. Tehtäväsi on käsitellä q kyselyä, joista jokainen liittyy tietyssä listan osassa oleviin lukuihin.

Jokaisessa kyselyssä sinun tulee ilmoittaa, montako paria luvuista voidaan muodostaa enintään niin, että jokaisessa parissa oikea luku on vähintään kaksinkertainen vasempaan lukuun verrattuna. Kukin luku saa kuulua enintään yhteen pariin.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja q.

Toisella rivillä on n kokonaislukua x_1,x_2,\dots,x_n: listan sisältö. Listan luvut ovat järjestyksessä pienimmästä suurimpaan.

Lopuksi tulee q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b: listan osa alkaa kohdasta a ja päättyy kohtaan b.

Tuloste

Tulosta jokaisen kyselyksen vastauksena, montako paria luvuista voidaan muodostaa enintään.

Esimerkki

Syöte:

8 4
1 2 2 4 7 8 8 8
1 4
2 3
4 8
1 8

Tuloste:

2
0
1
4

Selitys:

• Listasta [1,2,2,4] voidaan muodostaa kaksi paria (1,2) ja (2,4).
• Listasta [2,2] ei voida muodostaa yhtään paria.
• Listasta [4,7,8,8,8] voidaan muodostaa yksi pari (4,8).
• Listasta [1,2,2,4,7,8,8,8] voidaan muodostaa neljä paria (1,7), (2,8), (2,8) ja (4,8).

Osatehtävä 1 (16 pistettä)

• 1 \le n \le 2 \cdot 10^5
• 1 \le q \le 1000
• 1 \le x_i \le 100

Osatehtävä 2 (42 pistettä)

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

Osatehtävä 3 (42 pistettä)

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