Cho dãy ~𝐴~ gồm ~𝑛~ số nguyên dương ~𝑎_1, 𝑎_2, . . , 𝑎_𝑛~. Cho ~𝑞~ truy vấn có dạng ~𝑙~, ~𝑟~

Yêu cầu: Với mỗi truy vấn ~𝑙~, ~𝑟~ hãy đếm số lượng các số có giá trị dương từ phần tử thứ ~l~ đến phần tử thứ ~r~ của dãy số ~A~.

Dữ liệu vào:

• Dòng thứ nhất ghi 2 số nguyên dương ~𝑛~ và ~𝑞~ (~1 ≤ 𝑛,𝑞 ≤ 2.10^6~)
• Dòng thứ hai ghi ~𝑛~ số nguyên ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~ các số có giá trị tuyệt đối không vượt quá ~10^6~
• ~𝑞~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~𝑙~, ~𝑟~ (~1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛~)

Dữ liệu ra:

• ~𝑞~ dòng mỗi dòng ghi một số nguyên dương là kết quả tìm được của mỗi truy vấn.

Ví dụ

Input

9 3
1 -3 8 9 -7 -9 9 7 -1
1 6
2 7
6 9

Output

3
3
2