Little Elephant is playing a game with arrays. He is given an array A0, A1, ..., AN−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 Ai, Ai+1, ..., Aj  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 Ai, Ai+1, ..., Aj and Ak, Ak+1, ..., Al 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 A0, A1, ..., AN−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 ≤ Ai ≤ 1000000 (106)
- 1 ≤ Q ≤ 10
- 1 ≤ K ≤ 1000000 (106)

-----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 (A0 and A4) 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.

Difficulty: interview

Starter code:

Solutions:
import sys
import math

def main(arr,k):
    
    ans=0
    for i in range(len(arr)):
        curr_min=float('inf')
        for j in range(i,len(arr)):
            curr_min=min(curr_min,arr[j])
            
            if curr_min==k:
                ans+=1 
    return ans
        

n=int(input())
arr=list(map(int,input().split()))


for i in range(int(input())):
    
    print(main(arr,int(input())))

# cook your dish here
n=int(input())
arr=[int(i) for i in input().split()]
q=int(input())
for _ in range(q):
    val=int(input())
    if val not in arr:
        print(0)
    else:
        count=0
        for i in range(1,n+1):
            for j in range(n-i+1):
                if min(arr[j:j+i])==val:
                    count+=1
                    
        print(count)
        

# cook your dish here
n=int(input())
l=list(map(int,input().split()))
q=int(input())
for _ in range(q):
    x=int(input())
    c=0
    for i in range(n):
        for j in range(i+1,n+1):
            d=min(l[i:j])
            if(d==x):
                c+=1
    print(c)


# cook your dish here
n=int(input())
l=list(map(int,input().split()))
q=int(input())
for i in range(q):
    x=int(input())
    c=0
    for i in range(n):
        for j in range(i+1,n+1):
            d=min(l[i:j])
            if(d==x):
                c+=1
    print(c)


n = int(input())
arr = [int(i) for i in input().split()]
q = int(input())
for _ in range(q):
    sub = 0
    k = int(input())
    for i in range(n):
        for j in range(i+1,n+1):
            if min(arr[i : j]) == k:
                sub = sub + 1
    print(sub)

# cook your dish here
n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    x=0
    for i in range(0,len(a)):
        for j in range(i,len(a)):
            if k==min(a[i:j+1]):
                x=x+1
    print(x)

n=int(input())
l=list(map(int,input().split()))
d={}
for i in range(n):
    a=[]
    x=l[i]
    for j in range(i,n):
        a.append(l[j])
        x=min(x,l[j])
        if(x in d):
            d[x]+=1
        else:
            d[x]=1
q=int(input())
while(q>0):
    b=int(input())
    if(b in d):
        print(d[b])
    else:
        print(0)
    q-=1



n=int(input())
lis = list(map(int, input().split()))

q = int(input())
ans = []
res=[]
for i in range(len(lis)+1):
    ans=[]
    for j in range(i+1, len(lis)+1):
        ans=lis[i:j]
        res.append(ans)
    #print(res)
while q>0:
    k = int(input())
    count=0
    for i in range(len(res)):
        if k==min(res[i]):
            count+=1
    print(count)
    q-=1


n=int(input())
x=list(map(int,input().split()))
q=int(input())
for i in range(q):
    c=0
    k=int(input())
    for j in range(n):
        for l in range(j,n):
            if(min(x[j:l+1])==k):
                c+=1
    print(c)


n=int(input())
x=list(map(int,input().split()))
q=int(input())
for i in range(q):
    c=0
    k=int(input())
    for j in range(n):
        for l in range(j,n):
            if(min(x[j:l+1])==k):
                c+=1
    print(c)





# cook your dish here
n=int(input())
s1=input().split(' ')
l=[]
for _ in s1:
	l.append(int(_))
i=0
sub=[]
while(i<n):
	s=i
	f=i+1
	while(f<=n):
		l1=l[s:f]
		sub.append(l1)
		f+=1
	i+=1

q=int(input())
k=0
while(k<q):
	c=0
	q1=int(input())
	for e in sub:
		if(min(e)==q1):
			c+=1
	print(c)
	k+=1				

from sys import stdin, stdout
import numpy as np

n = int(input())
a = list(map(int, input().split()))
q = int(input())
while q:
    q -= 1
    k = int(input())
    ans = 0
    for i in range(n):
        flag = False
        count = 0
        forward = 0
        backward = 1
        if a[i] == k:
            if i != a.index(k):
                flag = True
            for j in range(i, n):
                if a[j] >= k:
                    forward += 1
                else:
                    break

            for j in range(i - 1, -1, -1):
                if flag:
                    if a[j] > k:
                        backward += 1
                    else:
                        break
                else:
                    if a[j] >= k:
                        backward += 1
                    else:
                        break
            count += forward * backward
            ans += count

    print(ans)


from sys import stdin, stdout
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
q = int(input())
while q:
    q -= 1
    k = int(input())
    ans = 0
    for i in range(n):
        for j in range(i + 1, n+1):
            if min(a[i:j]) == k:
                ans += 1
    print(ans)


N = int(input())
array = list(map(int, input().split()))
for _ in range(int(input())):
    K = int(input())
    count = 0
    for i in range(N):
        for j in range(i+1,N+1):
            if K == min(array[i:j]):
                count += 1
    print(count)

n = int(input())
l = list(map(int, input().split()))
for i in range(int(input())):
    c = 0
    quer = int(input())
    for i in range(n):
        for j in range(i+1, n+1):
            if min(l[i:j]) == quer:
                c += 1
    print(c)

array_size = int(input())
arr = input().split(" ")
arr = list(map(int, arr))
query_no = int(input())
for tc in range(query_no):
    k = int(input())
    count = 0
    result = [[]]
    for i in range(len(arr) + 1):
        for j in range(i+1, len(arr) + 1):
	        sub = arr[i:j]
	        result.append(sub)
    for i in result:
	    if i != []:
	        if k == (min(i)):
	            count += 1
    print(count)
	

# cook your dish here
input()
arr = list(map(int, input().split(' ')))
subarrays = []

temp_arr = []
for i in range(len(arr) - 1):
    for j in range(i, len(arr)):
        temp_arr.append(arr[j])
        subarrays.append(temp_arr.copy())
    temp_arr = []
subarrays.append([arr[-1]])

for query in range(int(input())):
    num = int(input())
    total = 0
    for subarr in subarrays:
        if min(subarr) == num:
            total += 1
    
    print(total)
    

# cook your dish here
input()

arr = list(map(int, input().split()))

Q = int(input())

for item in range(Q):
    K = int(input())
    
    total = 0
    for i in range(len(arr)):
        hasK = False
        if arr[i] >= K:
            if arr[i] == K:
                hasK = True
                total += 1
            j = i + 1
            while j < len(arr) and arr[j] >= K:
                if arr[j] == K:
                    hasK = True
                if hasK:
                    total += 1
                j += 1
                    
    print(total)

t=1
for _ in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    d={}
    for i in range(n):
        k=l[i]
        for j in range(i,n):
            k=min(k,l[j])
            try:
                d[k]+=1
            except:
                d[k]=1
    q=int(input())
    for _ in range(q):
        k=int(input())
        try:
            print(d[k])
        except:
            print(0)
    
    t-=1


n = int(input())
a = list(map(int,input().split()))

d = {}
for i in range(n):
	d[a[i]] = 0

for i in range(n):
	for j in range(i,n):
		l = a[i:j+1]
		d[min(l)] += 1

q = int(input())
for _ in range(q):
	x = int(input())
	if x in d:
		print(d[x])
	else:
		print(0)

N=int(input())
A=[int(x) for x in input().split()]
for _ in range(int(input())):
    K=int(input())
    total=0
    for i in range(N):
        a=0
        count=0
        forward=0
        backward=1
        if(A[i]==K):
            if(i!=A.index(K)):
                a=1
            for j in range(i,N):
                if(A[j]>=K):
                    forward+=1
                else:
                    break
            
            for j in range(i-1,-1,-1):
                if(a==1):
                    if(A[j]>K):
                        backward+=1
                        
                    else:
                        break
                elif(a==0):
                    if(A[j]>=K):
                        backward+=1
                        
                    else:
                        break
            
            count+=forward*backward
            total+=count
                    
    print(total)