有一個整數陣列A，有Q筆詢問。

每一筆詢問有兩個整數X,Y。

請輸出A中位於[X,Y]區間的數共有多少個。

輸入格式

第一行是一個數字n(\(1 \leq n \leq10^5\))，A的長度，接下來一行有n個整數(\(|A[i]| \leq 10^9\))表示A的內容。

第三行是一個數字Q(\(1 \leq Q \leq10^5\))，接下來Q行各有2個數字X，Y(\(|X,Y| \leq 10^9\))。

輸出格式

於第i行輸出第i次詢問的答案。

範例輸入

5
1 -5 -111 1548 0
3
11 151
0 0
0 20000

範例輸出

0
1
3