0.4 Queries

Score: 30pts

Time Limit: 5.00 sec

Your friend gives you an array and assigns a task. The task is as follows-

1) You are given a key element.

2) You will get ‘q’ queries. In each query, there will be an index and you have to tell how many times the particular key value has occurred in the array up to that index (inclusive). If the element at a given index is not equal to the given key then you have to print “0” or if it's a match then print the number of occurrences till the given index.

1) You are given a key element.

2) You will get ‘q’ queries. In each query, there will be an index and you have to tell how many times the particular key value has occurred in the array up to that index (inclusive). If the element at a given index is not equal to the given key then you have to print “0” or if it's a match then print the number of occurrences till the given index.

Constraints

1 <= t <= 10

1 <= n <= 10^5

1 <= arr[i] <= 10^5

1 <= key <= 10^5

1 <= q <= 10^5

0 <= ind < 10^9

1 <= n <= 10^5

1 <= arr[i] <= 10^5

1 <= key <= 10^5

1 <= q <= 10^5

0 <= ind < 10^9

Input Format

The first line contains an integer t - the number of test cases

Each test case contains the following lines-

The first line contains an integer n - the number of elements in the array.

The second line contains the array elements separated by space (arr).

The third line contains the key element.

The next line contains an integer q - the number of queries

For each query, there is a single line of input i.e. the index (ind)

Each test case contains the following lines-

The first line contains an integer n - the number of elements in the array.

The second line contains the array elements separated by space (arr).

The third line contains the key element.

The next line contains an integer q - the number of queries

For each query, there is a single line of input i.e. the index (ind)

Output Format

For each test case, print the expected output of each query in new line.

Example 1

Input:

1

8

1 4 5 4 3 4 6 2

4

3

1

5

6

Output:

1

3

0

Explanation:

There is just one test case.

For query 1: Index is 1 and a[1]==key and the count is 1.

For query 2: Index is 5 and a[5]==key and the count will be 3 because 4 has been repeated three times till index 5.

For query 3: Index is 6 but a[6]!=key so the answer is 0.

1

8

1 4 5 4 3 4 6 2

4

3

1

5

6

Output:

1

3

0

Explanation:

There is just one test case.

For query 1: Index is 1 and a[1]==key and the count is 1.

For query 2: Index is 5 and a[5]==key and the count will be 3 because 4 has been repeated three times till index 5.

For query 3: Index is 6 but a[6]!=key so the answer is 0.