Trắc nghiệm tâm lí

Trắc nghiệm tâm lí là phương pháp thông dụng để có thể đoán nhận được tính cách của mỗi người trong cuộc sống và cũng là một trò chơi khá phổ biến trên truyền hình. Trong một trò chơi như vậy được phát trên kênh VTV. Trước tiên, ban tổ chức phát cho mỗi khán giả ngồi xem trực tiếp một phiếu thăm dò trong đó có các câu hỏi trắc nghiệm. Tất cả các phương án trả lời đều có điểm và mỗi người sau khi trả lời xong sẽ được tổng hợp tổng điểm là một số nguyên dương. Có \(m\) người tham gia cuộc chơi trên sân khấu. Với người chơi thứ \(i\), sau khi nghe người dẫn chương trình đọc các câu hỏi trắc nghiệm sẽ đưa ra hai số \(s_i\) và \(f_i\) với ý nghĩa khán giả có tổng điểm nằm trong đoạn \([s_i, f_i]\) sẽ là những người có tính cách phù hợp với mình nhất.

Yêu cầu: Viết chương trình tính xem mỗi người chơi sẽ tìm thấy bao nhiêu khán giả có tính cách phù hợp với mình.

Input

Nhập từ bàn phím gồm:

• Dòng đầu tiên chứa số nguyên \(n\) (\(0 < n \le 10^5\)) là số khán giả.

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^5\)) là tổng điểm của mỗi khán giả.

• Dòng thứ ba chứa số nguyên \(m\) (\(1 \le m \le 10^5\)) là số người chơi.

• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(s_i, f_i\) (\(1 \le s_i \le f_i \le 10^5\)) là khoảng điểm của những người có tính cách phù hợp nhất với người \(i\) (\(1 \le i \le m\)).
  Hai số nguyên liên tiếp trên cùng một dòng cách nhau bằng dấu trống (space).

Ràng buộc:

• Có \(5\) trong \(8\) test (\(62{,}5\%\)) thỏa mãn \(n, m \le 5000\).

• Có \(3\) trong \(8\) test (\(37{,}5\%\)) còn lại thỏa mãn \(5000 < n, m \le 10^5\).

Output

In ra màn hình gồm \(m\) dòng, dòng thứ \(i\) ghi một số nguyên là số lượng khán giả có tính cách phù hợp với người thứ \(i\) (\(1 \le i \le m\)).

Example

Input:

5
7 2 4 5 3
2
1 4
3 10

Output:

3
4

Note

Có \(5\) khán giả với tổng điểm lần lượt là \(7, 2, 4, 5, 3\). Người chơi thứ nhất có đoạn \([1, 4]\): các khán giả có điểm \(2, 4, 3\) thuộc đoạn này nên đáp án là \(3\). Người chơi thứ hai có đoạn \([3, 10]\): các khán giả có điểm \(7, 4, 5, 3\) thuộc đoạn này nên đáp án là \(4\).