Little Elephant and Subarrays `SUBMIN`

All submissions for this problem are available.<h3> Read problems statements in Mandarin Chinese and Russian.</h3>

Little Elephant is playing a game with arrays. He is given an array A₀, A₁, ..., A_N−1 of N integers. And then Q queries are given, each containing an integer K. He has to tell how many subarrays satisfy the condition: the function foo returns K when it is applied to the subarray.
In this problem, a subarray is defined as a sequence of continuous elements A_i, A_i+1, ..., A_j where 0 ≤ i ≤ j ≤ N−1. The function foo, when applied to an array, returns the minimum of all the elements in the array.
For example, foo returns 5 when it is applied to the array [7, 5, 10, 7, 5, 8]. Please note that the subarrays A_i, A_i+1, ..., A_j and A_k, A_k+1, ..., A_l are different if and only if i ≠ k or j ≠ l in this problem.

Input

The first line of input contains N, denoting the size of the array. The next line contains N space separated integers A₀, A₁, ..., A_N−1, denoting the array. Then the next line contains Q, denoting the number of queries. Each query consists of one integer per line, denoting K.

Output

For each query, print the required number of subarrays.

Constraints

1 ≤ N ≤ 50
1 ≤ A_i ≤ 1000000 (10⁶)
1 ≤ Q ≤ 10
1 ≤ K ≤ 1000000 (10⁶)

Example

Input:
5
4 1 2 3 4
4
3
4
6
1

Output:
2
2
0
8

Explanation

Query 1. Only the two subarrays [3, 4] and [3] satisfy.

Query 2. Again only the two subarrays [4] and [4] satisfy. Please note that these subarrays (A₀ and A₄) are considered different.

Query 3. No subarray satisfies.

Query 4. The eight subarrays [4, 1], [4, 1, 2], [4, 1, 2, 3], [4, 1, 2, 3, 4], [1], [1, 2], [1, 2, 3] and [1, 2, 3, 4] satisfy.

Little Elephant and Subarrays SUBMIN