Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np
n = list(map(int, input().split()))
d = np.array(list(map(int, input().split())))

while 1:
    a = n[0] // 1000
    b = (n[0] % 1000) // 100
    c = (n[0] % 100) // 10
    e = n[0] % 10
    
    if np.any(d == a):
        n[0] = (a + 1) * 1000
    elif  np.any(d == b):
        n[0] = a * 1000 + b * 100
    elif np.any(d == c):
        n[0] = a * 1000 + b * 100 + c * 10
    elif np.any(d == e):
        n[0] += 1
    else:
        print(n[0])
        break

### FIXED CODE ###

import numpy as np

n = list(map(int, input().split()))
d = np.array(list(map(int, input().split())))
a = len(str(n[0]))
x = np.zeros(a + 1)

for i in range(a + 1):
    x[i] = (n[0] % np.power(10, a - i + 1)) // np.power(10, a - i)

i = 0
while i != a:
    i += 1
    while np.any(d == x[i]):
        x[i] += 1
        if i != a:
            x[i + 1:] = 0
        if x[i] == 10:
            x[i - 1] += 1
            x[i:] = 0
            i -= 1

ans = 0
for i in range(a + 1):
    ans += x[i] * np.power(10, a - i)

print(int(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)[::-1]
if k >= n:
    print(0)
else:
    for i in range(k):
        l.pop(0)
    s = sum(l)
    print(s)

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)[::-1]
if k >= n:
    print(0)
else:
    s=0
    for i in range(k,n):
        s+=l[i]
    print(s)
### BUGGY CODE ###

def main():
    # import sys
    # input = sys.stdin.readline
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]
    
    # print (d_list)
    # print (m_list)
    # print (c_list)
    # print (M_list)



    def calc(k):
        # d = 0
        # m = 0
        # c = 0
        # M = 0
        # for s in S[:k]:
        #     if s == 'D':
        #         d += 1
        #     elif s == 'M':
        #         m += d
        #         M += 1
        #     elif s == 'C':
        #         c += m
        # print (d, m, c)

        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            tmp = S[index]
            if tmp == 'D':
                m -= M
                d -= 1
            elif tmp == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

    for k in K:
        print (calc(k))

    # print (calc(5))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = tuple(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


if __name__ == "__main__":
    main()
### BUGGY CODE ###

H = int(input())

i = 1
sm = 1

while 1:
    H = H // 2

    sm += 2**i
    i += 1

    if H == 1:
        break

print(sm)

### FIXED CODE ###

H = int(input())

i = 1
sm = 1

if H == 1:
    print(1)
    exit()
else:
    while 1:
        H = H // 2
    
        sm += 2**i
        i += 1
    
        if H == 1:
            break

print(sm)
### BUGGY CODE ###

from operator import mul
from functools import reduce
 
def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def conv(st):
    res = [0]*26
    for s in st:
        res[ord(s)-ord('a')] += 1
    return ''.join(map(str,res))

N = int(input())
S = [conv(input()) for _ in range(N)]
setS = set(S)
res = 0
for s in setS:
    cnt = S.count(s)
    if cnt > 1:
        res += nCr(cnt, 2)
print(res)

### FIXED CODE ###

def conv(st):
    res = [0]*26
    for s in st:
        res[ord(s)-ord('a')] += 1
    return ''.join(map(str,res))

N = int(input())
S = {}
res = 0
for i in range(N):
    s = conv(input())
    if s not in S.keys():
        S[s] = 1
    else:
        S[s] += 1
    if S[s] > 1:
        res += S[s]-1
print(res)
### BUGGY CODE ###

prime = [3, 5]
for i in range(13, 102010, 12):
  r = int(i**(1/2))
  p = 0
  for j in range(2, r+1):
    if i % j == 0:
      p = 1
      break
  a = (i+1)//2
  r = int(a**(1/2))
  for j in range(2, r+1):
    if a % j == 0:
      p = 1
      break
  if p == 0:
    prime.append(i)

Q = int(input())
for i in range(Q):
  L = list(map(int, input().split()))
  L[0] -= 1
  i = 0
  while L[0] >= prime[i]:
    i += 1
  j = 0
  while L[1] >= prime[j]:
    j += 1
  print(j-i)

### FIXED CODE ###

prime = [3, 5]
for i in range(13, 102010, 12):
  r = int(i**(1/2))
  p = 0
  for j in range(2, r+1):
    if i % j == 0:
      p = 1
      break
  a = (i+1)//2
  r = int(a**(1/2))
  for j in range(2, r+1):
    if a % j == 0:
      p = 1
      break
  if p == 0:
    prime.append(i)
LL = []
j = 0
for i in range(100001):
  if i >= prime[j]:
    j += 1
  LL.append(j)

Q = int(input())
for i in range(Q):
  L = list(map(int, input().split()))
  L[0] -= 1
  print(LL[L[1]] - LL[L[0]])
### BUGGY CODE ###

from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    if a <= m:
        ab.append([a,b])
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)

### FIXED CODE ###

import sys
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for line in sys.stdin:
    a,b = map(int,line.split())
    if a <= m:
        ab.append([a,b])
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)
### BUGGY CODE ###

from bisect import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
count = 0
for i in range(N):
    minb = bisect(B, A[i])
    if minb == N:
        break
    for j in range(minb, N):
        if B[j] == A[i]:
            continue
        minc = bisect(C, B[j])
        if minc == N:
            break
        count += N - minc
print(count)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
print(sum(bisect.bisect_left(A, i)*(N-bisect.bisect_right(C, i)) for i in B))
### BUGGY CODE ###

N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    for j in range(sorted, i, -1):
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        sorted = j
        break

print(str(ans))

### FIXED CODE ###

N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    for j in range(sorted, i, -1):
      sorted = j - 1
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        break
  if (i + 1) > sorted:
    break
print(str(ans))
### BUGGY CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))


### FIXED CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))
### BUGGY CODE ###

from collections import deque
S = input()
s = deque(S)
Q = int(input())
for _ in range(Q):
    q = input()
    if q == "1":
        s.reverse()
    else:
        _, F, C = q.split()
        if F == "1":
            s.appendleft(C)
        else:
            s.append(C)
print("".join(s))

### FIXED CODE ###

S = input()
Q = int(input())
f = True
l = []
r = []
for _ in range(Q):
    q = input()
    if q == "1":
        f = not f
    else:
        _, F, C = q.split()
        if F == "1":
            t = l if f else r
            t.append(C)
        else:
            t = r if f else l
            t.append(C)
if f:
    l.reverse()
    ans = "".join(l) + S + "".join(r)
else:
    r.reverse()
    ans = "".join(r) + S[::-1] + "".join(l)
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
li=[]
for i in range(n//(a+b)+1):
  for k in range(a):
    li.append('b')
  for m in range(b):
    li.append('r')
print(li[:n].count('b'))


### FIXED CODE ###

n,a,b=map(int,input().split())
ans = n // (a + b) * a
rem = n % (a + b)
ans+=min(a,rem)
print(ans)
### BUGGY CODE ###

def solve(n,m,a,b):
    ans = 0
    lim = (a*n+b)//m
    
    for i in range(1,lim+1):
        l = (i*m-b+a-1)//a
        r = (i*m+m-b-1)//a

        ans += (min(r,n-1)-l+1)*i

    return ans

def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        print(solve(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()

### FIXED CODE ###

# def solve(n,m,a,b):
#     ans = 0
#     lim = (a*n+b)//m
    
#     for i in range(1,lim+1):
#         l = (i*m-b+a-1)//a
#         r = (i*m+m-b-1)//a

#         ans += (min(r,n-1)-l+1)*i

#     return ans

def floor_sum(n, m, a, b):
    ans = 0

    # (a*i+b)//m
    '''    
        k = a//m
        series 
            k + 2k + 3k + ... (n-1)k 
    '''
    if a>=m:
        ans += n*(n-1)*(a//m)//2
        a %= m


    '''
        k = b//m
        for each i

        series
            k + k + ... + k <n-1 times>
    '''
    if b>=m:
        ans += n*(b//m)
        b %= m

    yn = (a*n+b)//m

    if yn == 0:
        return ans #yn == 0 implies prev terms contibute 0 so return ans

    x_least = (yn * m - b) #the first x for which y(x) == yn 'x_least' refers to the val a*x.

    l = (x_least+(a-1))//a
    r = n-1 

    ans += (r-l+1)*yn  #if ans was not returned then this implies y(n) == y(n-1) == yn. element in window [l...r] have y(x) = yn
    ans += floor_sum(yn, a, m, (a-x_least%a)%a)
    return ans
    '''
    #r+1 as we pass the element that does not belong in the range.

    '''
def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        # print(solve(n,m,a,b))
        print(floor_sum(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,1,X])
        origST.append([T-X,-1,X])
    origST.sort()
    stidx = 0
    cur_set = set([])
    for idx in range(Q):
        q = int_raw()
        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > q:
                break
            if st[1]>0:
                cur_set.add(st[2])
            else:
                cur_set.remove(st[2])
            stidx+=1
        if len(cur_set)==0:
            print(-1)
        else:
            print (min(cur_set))

main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for q in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > q:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=q:
            heappop(cur_set)
        if len(cur_set)==0:
            print(-1)
        else:
            print(cur_set[0][0])
main()
### BUGGY CODE ###

n = int(input())
S = list(input())
min = n+1
for i in range(0, n):
    ans = S[:i].count('W')
    ans2 = S[i:].count('E')
    answer = ans + ans2
    if(answer < min):
        min = answer
print(min)

### FIXED CODE ###

n = int(input())
S = input()
w_num = S.count('W')
e_num = S.count('E')
a = 0
b = e_num
amin = n+1
if(len(set(S)) == 1):
    print(0)
else:
    for i in S:
        if(i == 'E'):
            b -= 1
        else:
            a+=1
        if(a+b < amin):
            amin = a+b
    print(min(amin, w_num, e_num))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    pl=0
    pr=N
    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and temp == s:
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1
        else:
            if (pc - pl) % 2 == 1 and temp == s:
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1


resolve()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
#入力処理
for i in range(m):
  data.append(input().split())
checkd = []
tmp = {}

wa = 0
for i in range(m):
  if data[i][1] == "WA":
    if int(data[i][0]) not in tmp:
      tmp[int(data[i][0])] = 0
    tmp[int(data[i][0])] += 1  
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    if int(data[i][0] ) not in tmp:
      tmp[int(data[i][0])] = 0  
    wa += tmp[int(data[i][0])]
    
print(counter,wa)

  
  



### FIXED CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
tmp = {}#問題番号をkeyとしてWAをカウント

wa = 0
#入力処理
for _ in range(m):
  a,b = input().split() #入力処理
  if b == "WA": #解答がWA→tmpに問題番号をkeyとしてカウント
    if int(a) not in tmp:
      tmp[int(a)] = 0
    if tmp[int(a)] != -1:
      tmp[int(a)] += 1
  if int(a) not in tmp: #WA無しのACの対応 
    tmp[int(a)] = 0
  if (( b == "AC") and (tmp[int(a)] != -1)):#解答がACでtmp[問題番号]が出力済みでない場合
    counter += 1
    #checkd.append(int(a))
    wa += tmp[int(a)] #問題番号aの値をWAの合計に加算
    tmp[int(a)] = -1 #問題番号aが加算済み


"""
for i in range(m):
  if data[i][1] == "WA":
    if int(data[i][0]) not in tmp:
      tmp[int(data[i][0])] = 0
    tmp[int(data[i][0])] += 1  
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    if int(data[i][0] ) not in tmp:
      tmp[int(data[i][0])] = 0  
    wa += tmp[int(data[i][0])]
"""    
print(counter,wa)
### BUGGY CODE ###

mountain = []
removed = []
while True:
    try:
        command = raw_input()
    except EOFError:
        pass
    if command.split()[0] == 'push':
        mountain.append(command.split()[1])
    elif command.split()[0] == 'pop':
        removed.append(mountain[-1])
        mountain.pop(-1)
    elif command.split()[0] == 'quit':
        print ' '.join(removed)

### FIXED CODE ###

mountain = []
removed = []
while True:
    command = raw_input()
    if command.split()[0] == 'push':
        mountain.append(command.split()[1])
    elif command.split()[0] == 'pop':
        removed.append(mountain[-1])
        mountain.pop(-1)
    elif command.split()[0] == 'quit':
        break
for block in removed:
    print block
### BUGGY CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))