Little Elephant and Subarrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Elephant is playing a game with arrays. He is given an array A_{0}, A_{1}, ..., 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_{0}, A_{1}, ..., 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^{6})
 1 ≤ Q ≤ 10
 1 ≤ K ≤ 1000000 (10^{6})
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_{0} and A_{4}) 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.
Author:  darkshadows 
Tester:  gerald 
Editorial  http://discuss.codechef.com/problems/SUBMIN 
Tags  darkshadows 
Date Added:  3012014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 