For a given sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ which is sorted by ascending order, find the lower bound for a specific value $k$ given as a query.

* lower bound: the place pointing to the first element greater than or equal to a specific value, or $n$ if there is no such element.

Constraints

* $1 \leq n \leq 100,000$
* $1 \leq q \leq 200,000$
* $0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
* $0 \leq k_i \leq 1,000,000,000$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$


The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.

Output

For each query, print the position $i$ ($i = 0, 1, ..., n$) of the lower bound in a line.

Example

Input

4
1 2 2 4
3
2
3
5


Output

1
3
4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
from bisect import bisect_left
n = int(input())
a = tuple(map(int, sys.stdin.readline().split()))
q = int(input())
l = len(a)
for k in sys.stdin:
	k = int(k.strip())
	if k > a[-1]:
		print(l)
	else:
		print(bisect_left(a, k))


import bisect
input()
A = list(map(int, input().split()))
n = int(input())
for _ in range(n):
	x = int(input())
	bi = bisect.bisect_left(A, x)
	print(bi)


from bisect import bisect_left
n = int(input())
A = [int(a) for a in input().split()]
for _ in range(int(input())):
	i = bisect_left(A, int(input()))
	print(n if i == n else i)


import bisect
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = int(input())
	print(bisect.bisect_left(A, query))


import bisect

def main():
	n = int(input())
	li = [int(a) for a in input().split()]
	q = int(input())
	for _ in range(q):
		k = int(input())
		i = bisect.bisect_left(li, k)
		print(i)
main()


def binarySearch(n, a):
	ok = len(a)
	ng = -1
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if a[mid] >= n:
			ok = mid
		else:
			ng = mid
	return ok

def resolve():
	import sys
	input = sys.stdin.readline
	n = int(input())
	a = [int(i) for i in input().split()]
	q = int(input())
	for _ in range(q):
		k = int(input())
		print(binarySearch(k, a))
resolve()


import bisect
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect.bisect_left(A, k))


import bisect
n = int(input())
A = [int(x) for x in input().split()]
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect.bisect_left(A, k))


def solve():
	from sys import stdin
	f_i = stdin
	n = int(f_i.readline())
	A = list(map(int, f_i.readline().split()))
	q = int(f_i.readline())
	from bisect import bisect_left as bl
	print('\n'.join((str(bl(A, int(f_i.readline()))) for i in range(q))))
solve()


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k))


import bisect
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	k = int(input())
	if a[0] > k:
		print(0)
	elif k > a[n - 1]:
		print(n)
	else:
		L = bisect.bisect_left(a, k)
		print(L)


from bisect import bisect_left

def run():
	n = int(input())
	a = [int(x) for x in input().split()]
	assert n == len(a)
	q = int(input())
	for _ in range(q):
		k = int(input())
		i = bisect_left(a, k)
		print(i)
run()


from bisect import *
input()
L = [int(x) for x in input().split()]
n = int(input())
for _ in range(n):
	x = int(input())
	print(bisect_left(L, x))


import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
a.append(1e+20)
for i in range(int(input())):
	print(min(n, bisect.bisect_left(a, int(input()))))


from bisect import bisect
n = int(input())
a = list(map(lambda x: int(x), input().split()))
num_query = int(input())
for _ in range(num_query):
	k = int(input())
	print(f'{bisect(a, k - 1)}')


from bisect import bisect_left
n = int(input())
a = [*map(int, input().split())]
q = int(input())
while q:
	q -= 1
	k = int(input())
	print(bisect_left(a, k))


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k))


import sys
import bisect
input()
arr = list(map(int, input().split()))
nq = int(input())
lines = sys.stdin.readlines()
ans = [None] * nq
for i in range(nq):
	ans[i] = str(bisect.bisect_left(arr, int(lines[i])))
print('\n'.join(ans))


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k))


import sys
input = sys.stdin.readline

def LowerBound(d, l):
	max = len(l) - 1
	min = 0
	mid = max // 2
	while True:
		if l[mid] > d:
			max = mid
		elif l[mid] == d:
			while l[mid] == d and mid >= 0:
				mid -= 1
			return mid + 1
		else:
			min = mid
		mid = (max + min) // 2
		if mid == max or mid == min:
			if l[mid] == d or l[max] == d:
				while l[mid] == d and mid >= 0:
					mid -= 1
				return mid + 1
			if l[max] < d:
				return len(l)
			if l[mid] > d:
				return min
			return max

def main():
	nl = int(input())
	l = list(map(int, input().split()))
	for i in range(int(input())):
		n = int(input())
		result = LowerBound(n, l)
		print(result)
main()


import bisect
n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect.bisect_left(a, k))


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k))


from bisect import bisect_left
n = int(input())
A = tuple(map(int, input().split()))
q = int(input())
for _ in range(q):
	k = int(input())
	print(bisect_left(A, k))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
k = []
for i in range(q):
	k1 = int(input())
	k.append([k1, i])
a.sort()
k.sort()
ans = [n] * q
i = 0
j = 0
while i < q and j < n:
	try:
		while k[i][0] > a[j]:
			j += 1
	except:
		pass
	ans[k[i][1]] = j
	i += 1
for i in range(q):
	print(ans[i])


from bisect import bisect
readline = open(0).readline
N = int(readline())
(*A,) = map(int, readline().split())
open(1, 'w').writelines(['%d\n' % bisect(A, int(readline()) - 1) for q in range(int(readline()))])


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k))


import bisect
n = int(input())
num = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	k = int(input())
	if k > num[-1]:
		print(n)
		continue
	else:
		print(bisect.bisect_left(num, k))


from bisect import *
n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	k = int(input())
	print(bisect_left(box, k))


import bisect

def main():
	n = int(input())
	A = list(map(int, input().split()))
	q = int(input())
	for _ in range(q):
		b = int(input())
		index = bisect.bisect_left(A, b)
		print(index)
main()


import bisect
input()
A = list(map(int, input().split()))
for _ in [0] * int(input()):
	print(bisect.bisect_left(A, int(input())))