Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in n different shops in the city. It's known that the price of one bottle in the shop i is equal to x_{i} coins.

Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent m_{i} coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of shops in the city that sell Vasiliy's favourite drink.

The second line contains n integers x_{i} (1 ≤ x_{i} ≤ 100 000) — prices of the bottles of the drink in the i-th shop.

The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of days Vasiliy plans to buy the drink.

Then follow q lines each containing one integer m_{i} (1 ≤ m_{i} ≤ 10^9) — the number of coins Vasiliy can spent on the i-th day.


-----Output-----

Print q integers. The i-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the i-th day.


-----Example-----
Input
5
3 10 8 6 11
4
1
10
3
11

Output
0
4
1
5



-----Note-----

On the first day, Vasiliy won't be able to buy a drink in any of the shops.

On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.

On the third day, Vasiliy can buy a drink only in the shop number 1.

Finally, on the last day Vasiliy can buy a drink in any shop.

Difficulty: interview

Starter code:

Solutions:
import bisect
n = int(input())
p = list(map(int, input().split()))
p.sort()
q = int(input())
for i in range(q):
    c = int(input())
    print(bisect.bisect_right(p, c))
    


from bisect import bisect_right

n = int(input())
x = list(map(int, input().split()))
q = int(input())
x.sort()
for i in range(q):
    m = int(input())
    print(bisect_right(x, m))

from bisect import bisect
n = int(input())
shops = [int(i) for i in input().split()]
shops.sort()
q = int(input())
for _ in range(q):
    m = int(input())
    print(bisect(shops, m))


from bisect import bisect_right
def main():
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	q = int(input())
	for i in range(q):
		m = int(input())
		res = bisect_right(x, m)
		print(res)





def __starting_point():
	main()
__starting_point()

import bisect
n = int(input())
x = [int(x) for x in input().split()]
q = int(input())
x.sort()
s = ''
for i in range(q):
    m = int(input())
    t = bisect.bisect(x, m)
    s += str(t) + '\n'
print(s)

def UpperBound(A, key):
    left = -1
    right = len(A)
    while right > left + 1:
        middle = (left + right) // 2
        if A[middle] > key:
            right = middle
        else:
            left = middle
    return right

n = int(input())
N = sorted(list(map(int,input().split())))
q = int(input())

M = [0] * q

for i in range(q):
    m = int(input())
    print(UpperBound(N, m))



def b_s(a, key):
    left = -1
    right = len(a)

    while right - left > 1:
        m = (left + right) // 2
        if a[m] > key:
            right = m
        else:
            left = m
    return right

n = int(input())
cost = sorted(list(map(int, input().split())))
q = int(input())

for i in range(q):
    m = int(input())
    x = b_s(cost, m)
    print(x)

#!/usr/bin/env python3

from bisect import bisect

n = int(input())
x = sorted([int(x) for x in input().split()])
q = int(input())
for _ in range(q):
    m = int(input())
    print(bisect(x, m))



#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

n   = int(input())
x   = [int(i) for i in input().split()]

q   = int(input())


x   = sorted(x)
buy = [0]
j   = 0

for i in range(1, x[n-1]+1):
    s = 0
    while(j < n and x[j] == i ):
        s += 1
        j += 1
    buy.append(buy[i-1] + s)

ans = []
for i in range(q):
    m = int(input())
    if m < len(buy):
        ans.append(buy[m])
    else:
        ans.append(n)

start = time.time()

for i in range(q):
    print(ans[i])

finish = time.time()
#print(finish - start)


from bisect import bisect
t = input
p = print
r = range
n = int(t())
x = list(map(int, t().split()))
q = int(t())
a = [0] * q
for i in r(q):
    a[i] = int(t())

x.sort()
for i in a:
    index = bisect(x, i)
    p(index)

import bisect

n = int(input())
x = [int(x) for x in input().split()]
q = int(input())
x.sort()
for i in range(q):
    m = int(input())
    print(bisect.bisect_right(x,m))

def bp(n, t):
	l = 0
	r = n
	while r - l > 1:
		m = l + (r - l) // 2
		if x[m] <= t:
			l = m
		else:
			r = m
	if x[l] > t:
		l = -1
	return l + 1

n = int(input())
x = [int(i) for i in input().split()]
x.sort()
q = int(input())
for k in range(q):
	tmp = int(input())
	print(bp(n, tmp))
	


def bin_search(a):
    nonlocal prices
    nonlocal n
    l, r = 0, n - 1
    while l < r:
        m = (l + r + 1) // 2
        if prices[m] <= a:
            l = m
        else:
            r = m - 1
    return l


n = int(input())
prices = sorted(list(map(int, input().split())))
q = int(input())
for i in range(q):
    money = int(input())
    ans = bin_search(money)
    print(ans + 1 if money >= prices[0] else 0)


import bisect

n = int(input())
x = list(map(int, input().split()))
q = int(input())

x.sort()

x0 = min(x)
x1 = max(x)

for i in range(q):
    m = int(input())
    if m < x0:
        print(0)
    elif m > x1:
        print(n)
    else:
        print(bisect.bisect_left(x, m+1))


def binarysearch(A, key):
    l = -1
    r = len(A)
    while r > l+1:
        m = (l + r) // 2
        if A[m] > key:
            r = m
        else:
            l = m
    return l

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
m = int(input())
t = []
for i in range(m):
	x = int(input())
	t.append(binarysearch(lst, x))
for i in t:
	print(i+1)



import sys
line = sys.stdin.readlines()
n = int(line[0])
x = list(map(int, line[1].split()))
x.sort()

q = int(line[2])
y = []
for i in range(q):
    y.append((int(line[i+3]), i))
y.sort()

ans = []
j = 0
cnt = 0
for m, i in y:
    while j < n and m >= x[j]:
        cnt += 1
        j += 1
    ans.append((i, cnt))
ans.sort()

for i, a in ans:
    print(a)


n = int(input())
x = list(map(int, input().split(" ")))
x.sort()
q = int(input())
m = list()

for i in range(q):
	m_i = int(input())
	m.append([i, m_i, 0])

m.sort(key = lambda x: x[1])
# print(m)

i = 0
j = 0
count = 0
while j < q:
	if i == n:
		m[j][2] = count
		j += 1
		continue

	if x[i] <= m[j][1]:
		count += 1
		i += 1
	else:
		m[j][2] = count
		j += 1


m.sort(key = lambda x: x[0])
# print(m)
for x in m:
	print(x[2])

def bs(arr,m):
    n=len(arr)    
    low = 0
    high = n 
    while (low != high):
        mid = (low + high) // 2
        if (arr[mid] <= m):
            low = mid + 1
        else:
            high = mid
    return low

n=int(input())
ip=list(map(int,input().split()))
ip=sorted(ip)
for i in range(int(input())):
    m=int(input())
    print(bs(ip,m))


n = int(input())
x = [int(i) for i in input().split()]
x = sorted(x)
q = int(input())
import bisect
def upperbound(m):
	ind = bisect.bisect(x,m)
	return ind
		

for i in range(q):
	m = int(input())
	print(upperbound(m))

import bisect

n_shops = int(input())
prices = [int(x) for x in input().split(' ')]
prices.sort()
n_days = int(input())
for day in range(n_days):
    coins = int(input())
    N = bisect.bisect(prices, coins)
    print(N)




from sys import stdin,stdout

nbMagasins=int(stdin.readline())
prix=list(map(int,stdin.readline().split()))
prix.sort()
q=int(stdin.readline())

for i in range(q):
    prixMax=int(stdin.readline())

    inf=0
    sup=nbMagasins-1

    while sup>inf:
        milieu=(inf+sup)//2
        if prix[milieu]>prixMax:
            sup=milieu
        else:
            inf=milieu+1

    if prixMax<prix[0]:
        print(0)
    elif prixMax>=prix[-1]:
        print(nbMagasins)
    else:
        print(inf)



n=int(input())
ls=sorted(map(int,input().split()))
q=int(input())
l=[0]*(ls[-1]+1)
for x in ls:
    l[x]+=1
for i in range(1,ls[-1]+1):
    l[i]+=l[i-1]
ans=[]
for _ in range(q):
    x=int(input())
    if x<=ls[-1]:
        ans+=[str(l[x])]
    else:
        ans+=[str(l[-1])]
print('\n'.join(ans))

import bisect

n = int(input())
x = list(map(int, input().split()))
x.sort()
q = int(input())
a = []
for i in range(q):
    v = int(input())
    i = bisect.bisect_right(x, v)
    print(i)