Count Elements with Frequency At Least K

You are given an array \(A\) of \(n\) integers and an integer \(k\). Your task is to answer \(q\) queries. Each query provides two integers \(l\) and \(r\) (1-indexed) describing a subarray \(A[l\dots r]\). For each query, you must count the number of distinct elements in the subarray that appear at least \(k\) times.

Example:

For \(A = [1, 2, 2, 1, 2, 2, 1, 3]\) and \(k = 3\):

• Query (1, 4): The subarray is [1, 2, 2, 1]. Neither element appears 3 or more times, so the answer is 0.
• Query (2, 6): The subarray is [2, 2, 1, 2, 2]. Here, 2 appears 4 times, so the answer is 1.
• Query (3, 8): The subarray is [2, 1, 2, 2, 1, 3]. Again, only 2 appears at least 3 times, so the answer is 1.

Use standard input and output for processing the data.

inputFormat

The input is given in the following format from standard input:

1. The first line contains two integers \(n\) and \(k\), where \(n\) is the number of elements in the array and \(k\) is the frequency threshold.
2. The second line contains \(n\) space-separated integers representing the array \(A\).
3. The third line contains a single integer \(q\) representing the number of queries.
4. The next \(q\) lines each contain two integers \(l\) and \(r\) (1-indexed) which denote the bounds of the subarray for the query.

outputFormat

For each query, print a single line containing one integer – the number of distinct elements in the corresponding subarray \(A[l\dots r]\) that appear at least \(k\) times.

## sample

8 3
1 2 2 1 2 2 1 3
3
1 4
2 6
3 8

0
1
1

</p>