Cho một dãy ~n~ số nguyên ~a_1,a_2, ... , a_n~ (~n \leq 10^6, |a_i| \leq 10^9~)

Yêu cầu

Số lượng phần tử âm thuộc đoạn [~L,R~]

Dữ liệu

Cho từ file "ARR_A7.INP"

-Dòng đầu chứa hai số nguyên dương ~n, Q~, trong đó ~Q~ là số lượng testcase

-Dòng tiếp theo chứa ~n~ số nguyên ~a_1,a_2, ... , a_n~

-Q dòng tiếp theo mỗi dòng chứa cặp số ~L,R~

Kết quả

Ghi ra file "ARR_A7.OUT" Q dòng, mỗi dòng tương ứng là số phần tử âm thuộc đoạn [~L,R~]

Ví dụ

Input

5 2

4 -2 1 -3 6

1 3

2 5

Output

1

2

Giới hạn

-40% số test có ~n \leq 10^3, |a_i| \leq 10^3~

-30% số test có ~n \leq 10^5, |a_i| \leq 10^6~

-30% số test có ~n \leq 10^6, |a_i| \leq 10^9~