오름차순으로 정렬된 수열에서, 입력받은 두 수 사이(두 수 포함)에 있는 숫자의 개수를 구하는 프로그램을 작성하시오.

단, 수열에는 동일한 수가 여러 개 존재할 수 있으며, 구간을 구하는 질문은 총 k번 주어집니다.

입력

첫째 줄에 배열의 길이 n이 주어진다.

둘째 줄에 n개의 정수가 공백으로 구분되어 오름차순으로 입력된다.

셋째 줄에 두 수가 입력되는 횟수 k가 주어진다.

넷째 줄부터 k개의 줄에 걸쳐 각 줄마다 찾고자 하는 구간의 두 수 a와 b가 공백을 사이에 두고 주어진다.

출력

질문이 주어진 순서대로, k개의 줄에 걸쳐 각 줄마다 입력받은 두 수 사이(두 수 포함)에 있는 원소의 개수를 출력한다.

제한 사항

• 2 ≤ n ≤ 500,000
• 수열의 원소: 0 ≤ 원소 ≤ 500,000
• 1 ≤ k ≤ 10,000
• -1,000,000 ≤ a ≤ b ≤ 1,000,000

예제 입력 1

5
1 2 3 4 5
3
1 2
2 4
5 6

예제 출력 1

2
3
1