Problem:

Range Count Query

数列a_1,a_2,..,a_Nが与えられます。

クエリでは、値がl以上r以下の項の個数を答えてください。

入力

N Q
a_1 a_2...a_N
l_1 r_1
l_2 r_2
:
l_q r_q

出力

ans_1
ans_2
:
ans_q

i行目には、i番目のクエリに対する答え、すなわちl_i \leq a_j \leq r_iなるjの個数を出力せよ。

制約

  
1 \leq N,Q \leq 10^5 

  
1 \leq a_i \leq 10^9

  
1 \leq l_i \leq r_i \leq 10^9

入力例

6 3
8 6 9 1 2 1
2 8
1 7
3 5

出力例

3
4
0



Sample input:
6 3
8 6 9 1 2 1
2 8
1 7
3 5


Sample output:
3
4
0

Submission status: Accepted

Solution code:
def num():
    return int(input())
def nums():
    return list(map(int,input().split()))
"""
N = num()
A = nums()
print(A.index(min(A))+1)
"""
"""
N = num()
A =  set(nums())
print(len(A))
"""

def get_near_index(sorted_l,val,last):
    left = 0
    right = len(sorted_l) - 1
    while left <= right:
        mid = (right + left) // 2
        if sorted_l[mid] == val:
            return mid if last else mid
        elif sorted_l[mid] > val:
            right = mid -1
        else: 
            left = mid + 1
    return right if last else left 

N,Q = nums()
A = nums()
A.sort()
L,R = [],[]

for i in range(Q):
    li,ri = nums()
    L.append(li)
    R.append(ri)
for l,r in zip(L,R):
    l_idx = get_near_index(A,l,0)
    r_idx = get_near_index(A,r,1)
    print(r_idx-l_idx+1)