Problem:

Lower Bound

 

  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.
  

  

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.

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$

Sample Input 1

4
1 2 2 4
3
2
3
5

Sample Output 1

1
3
4



Sample input:
4
1 2 2 4
3
2
3
5


Sample output:
1
3
4

Submission status: Wrong Answer

Solution code:
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_right(a, k))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:

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)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# AOJ ITP2_6_C: Lower Bound
# Python3 2018.6.24 bal4u

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

Submission status: Accepted

Solution code:
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()))])

Submission status: Accepted

Solution code:
def binarySearch(n, a):
    ok = len(a)
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        # print("n:", n, "idx:", mid, "val:", a[mid], ok, ng, file=sys.stderr)
        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()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int,input().split())))
a.append(1e20)

for i in range(int(input())):
    print(min(n,bisect.bisect_left(a,int(input()))))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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) )

Submission status: Accepted

Solution code:
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 #k
j = 0 #a

while i<q and j<n:
    try:#j=nの処理
        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])

Submission status: Accepted

Solution code:
from bisect import bisect


if __name__ == "__main__":
    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)}")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Binary Search - Lower Bound
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_C&lang=jp

"""
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)

Submission status: Accepted

Solution code:
import bisect

if __name__ == '__main__':

	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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_C&lang=jp
#  Lower Bound : python3
#  2018.11.26 yonezawa

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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()))])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))