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

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

import numpy as np

S=[np.zeros(N) for i in range(26)]
for p,c in enumerate(s):
    for i in range(26):
        if i==ord(c)-65:
            S[i][p]=1
S1=np.ones(N)

from functools import reduce
g=np.ones(N)
for q in td:
    g_stable=g*np.logical_not(S[ord(q[0])-65])
    if q[1]=='L':
        g_move=np.append((g*S[ord(q[0])-65])[1:],0)
    else:
        g_move=np.insert((g*S[ord(q[0])-65])[:-1],0,0)
    g=g_stable+g_move
print(int(np.sum(g)))

### FIXED CODE ###

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

def move(s,td,position):
    p=position
    for spell in td:
        if s[p]==spell[0] and spell[1]=='L':
            p-=1
        elif s[p]==spell[0] and spell[1]=='R':
            p+=1
        if p<0 or p>=N: break
    return p

l=0
r=N-1
watched=[0]*N
while(True):
    p=(r+l)//2
    if watched[p]>0:
        if p<N-1 and watched[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res<0:
        l=p
        watched[p]=1
    else:
        r=p
        if watched[p]==0: watched[p]=2
ans_l=N
for i in range(N):
    if watched[i]==2:
        ans_l=i
        break

l=0
r=N-1
watched2=[0]*N
while(True):
    p=(r+l)//2
    if watched2[p]>0:
        if p<N-1 and watched2[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res>=N:
        r=p
        watched2[p]=3
    else:
        l=p
        if watched2[p]==0: watched2[p]=2
ans_r=-1
for i in range(N-1,-1,-1):
    if watched2[i]==2:
        ans_r=i
        break
print(max(0,ans_r-ans_l+1))
### BUGGY CODE ###



N = int(input())
S = input()
#N = 8
#S = 'WWWWWEEE'


min = 1000000
for i in range(1,N):
    l = S[i]
    if l == 'W':
        left = S[0:i-1].count('W')
        right = S[i+1:].count('E')
    else:
        left = S[0:i-1].count('W')
        right = S[i+1:].count('E')
    sum = right + left
    #print(l, sum, left, right)
    if min > sum:
        min = sum
print(min)



### FIXED CODE ###



N = int(input())
S = input()
#N = 12
#S = 'WEWEWEEEWWWE'


min = 1000000
e = S.count('E')
w = 0

for i in range(0,N):
    flag = 0
    now = S[i]
    if now == 'E':
        e = e - 1
    else:
        flag = 1
    sum = w + e
    if min > sum:
        min = sum
    if flag:
        w = w + 1
print(min)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


K = int(input())
x=0
for i in range(K):
    for j in range(K):
        g1=gcd(i+1,j+1)
        for k in range(K):
            g2=gcd(g1,k+1)
            x=x+g2
            #print("{}".format(g))
print("{}".format(x))


### FIXED CODE ###

# -*- coding: utf-8 -*-

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


K = int(input())
G = [[0]*K for i in range(K)]
x=0
for i in range(K):
    for j in range(K):
        g1=gcd(i+1,j+1)
        G[i][j]=g1

for i in range(K):
    for j in range(K):
        for k in range(K):
            g1=G[i][j]
#            print("{}".format(g1))
            x=x+G[g1-1][k]
#        for k in range(K):
#            g2=gcd(g1,k+1)
#            x=x+g2
            

print("{}".format(x))
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [[0] * 2 for _ in range(S + 1)]

    for x in A:
        for s in range(S, 0, -1):
            dp[s][1] = (dp[s][1] + dp[s][0]) % MOD
            if s - x >= 0:
                v = dp[s - x][0] + (1 if s - x == 0 else 0)
                dp[s][0] = (dp[s][0] + v) % MOD
                dp[s][1] = (dp[s][1] + v) % MOD

        dp[0][0] += 1
        dp[0][1] += (dp[0][0] + 1)

    print(dp[S][1])


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

import itertools
import sys

ans_list = []

while 1:
    ab = raw_input()
    if ab != "":
        a, b= map(int, ab.split())
    else:
        for s in ans_list:
            print s
        break
    GCD = a * b
    LCM = 0
    # GCD
    for i, j in itertools.product(range((a if a > b else b) / 2), repeat=2):
        if a * (i+1) == b * (j+1) and GCD > a * (i+1):
            GCD = a * (i+1)
    # LCM
    for i in range(a if a > b else b, 1, -1):
        if a % i == 0 and b % i == 0:
            LCM = i
            break
    ans_list.append(str(GCD) + " " + str(LCM))

sys.exit()

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_set = sorted(set(A_list))

A_output = [0 for i in range(N)]

for i in range(len(A_set)):
    A_output[A_set[i]-1] = A_list.count(A_set[i])
    
for i in range(len(A_output)):
    print(A_output[i])

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split()))
A_collection = collections.Counter(A_list)

for i in range(N):
    print(A_collection[i+1])
### BUGGY CODE ###

N, M=map(int, input().split())


ACs=[]
WAs={}

AC=0
pena=0
for i in range(M):
  num, jud=input().split()
  if num in ACs:
    continue
  elif jud=="WA":
    try:
      WAs[num]+=1
    except:
      WAs[num]=1
  else:
    ACs.append(num)
    AC+=1
    if num in WAs.keys():
      pena+=WAs[num]

print(AC, pena)



### FIXED CODE ###

N, M=map(int, input().split())
import numpy as np

pena=np.array([0]*N)
status=np.array([0]*N)


for i in range(M):
  p,s=tuple(input().split())
  p=int(p)
  if s=="WA":
    if status[p-1]!=1:
      pena[p-1]+=1
  if s=="AC":
    if status[p-1]!=1:
      status[p-1]=1
nac=sum(status)
npena=sum(pena*status)
print(nac, npena)
### BUGGY CODE ###

import math as m

K = int(input())

res = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            res += m.gcd(m.gcd(a, b), c)

print(res)


### FIXED CODE ###

import math as m

K = int(input())

res = 0
for a in range(1, K + 1):
    for b in range(a, K + 1):
        for c in range(b, K + 1):
            if a == b == c:
                res += a
            elif (a == b and a != c) or (b == c and b != a) or (a == c and a != b):
                res += m.gcd(max(a, b, c), min(a, b, c)) * 3
            else:
                res += m.gcd(m.gcd(a, b), c) * 6

print(res)
### BUGGY CODE ###

from collections import deque

N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))

for k in K:
    res = 0
    D = deque()
    M = deque()
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            D.append(i)
        if S[i] == 'M':
            dm += len(D)
            if D:
                M.append(i)
        if S[i] == 'C':
            res += dm
        if D and D[0] + k <= i + 1:
            d = D.popleft()
            dm -= len(M)
            if D:
                while M and D[0] > M[0]:
                    M.popleft()
            else:
                M = deque()
                dm = 0

    print(res)

### FIXED CODE ###

from collections import deque

N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))

for k in K:
    res = 0
    d = 0
    m = 0
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            dm += d
            m += 1
        elif S[i] == 'C':
            res += dm
        if i + 1 - k >= 0:
            if S[i + 1 - k] == 'D':
                d -= 1
                dm -= m
            elif S[i + 1 - k] == 'M':
                m -= 1

    print(res)
### BUGGY CODE ###

# coding:utf-8
# Doubly Linked List

class DLL:

    def __init__(self):
        self.array = []

    def insert(self, x):
        self.array = [x] + self.array
    
    def delete(self, x):
        try:
            del self.array[self.array.index(x)]
        except:
            pass

    def deleteFirst(self):
        del self.array[0]

    def deleteLast(self):
        del self.array[len(self.array)-1]


def main():

    dll = DLL()
    n = int(input())
    ans = ""

    for _ in range(n):
        operation = input().split()
        command = operation[0]
        if command in ["insert", "delete"]:
            key = operation[1]
            eval("dll." + command + '(' + key + ')')

        else:
            eval("dll." + command + "()")
    for value in dll.array:
        ans += str(value) + " "

    print(ans.rstrip())

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

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

N = int(input())
C = list(map(int, input().split()))

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = 2 ** (N - 1)
d = 2 ** (N - 2)
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))

### FIXED CODE ###

N = int(input())
C = list(map(int, input().split()))

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = pow(2, N - 1, MOD)
d = pow(2, N - 2, MOD) if N - 2 >= 0 else 0
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
for i in c_set:
  if A.count(i) > 1:
    d += 1

print(ans - d)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit, prange

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True, parallel = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in prange(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        vs = []
        ws = []
        while V >= n:
            vs.append(vws[V][0])
            ws.append(vws[V][1])
            V = (V-1) // 2
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

def main():
    
    N = int(input())
    A = [int(input()) for _ in range(N)]

    A = np.array(A)

    for i in range(N):
        print(max(np.delete(A, [i], axis=0)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a = int(input())
    lists= [int(input()) for _ in range(a)]
 
    temp = lists.copy()
    first = max(temp)
    temp.remove(first)
    second = max(temp)
 
    for i in range(a):
        if lists[i] == first:
            print(second)
        else:
             print(first)
 
if __name__ == '__main__' :
    main()
### BUGGY CODE ###

s = input()
s = s.replace("BC","D").replace("B","E").replace("C","E")
s = s.split("E")

def solve(s):
    ans = 0
    while "AD" in s:
        ans += s.count("AD")
        s = s.replace("AD","DA")
    return ans

ans = 0
for ele in s: ans += solve(ele)
print(ans)


### FIXED CODE ###

s = input()
s = s.replace("BC","D").replace("B","E").replace("C","E")
s = s.split("E")

def solve(s):
    ans = 0 ; tmp = 0
    for char in s:
        if char == "A": tmp += 1
        else: ans += tmp
    return ans

ans = 0
for ele in s: ans += solve(ele)
print(ans)
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
idx = 0
for i in range(N - 1):
    a.insert(2+idx, a.pop())
    idx += 3
print(sum(a[1::3]))

### FIXED CODE ###

N = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[1:len(a)-N:2]))
### BUGGY CODE ###

from collections import Counter

N = int(input())

s = [[] for _ in range(N)]
check = []
ans = []
for x in range(N):
    for c in input():
        s[x].append(c)

for x in s:
    check.append(Counter(x))

for x in range(N):
    for y in range(x+1,N):
        ans.append(dict(check[x])==dict(check[y]))


print(sum(ans))

### FIXED CODE ###

from collections import Counter

N = int(input())

# check = []
# ans = {}
# answer = 0
# for _ in range(N):
#     s = Counter(input())
#     if s not in check:
#         check.append(s)
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] = 0
#
#     else:
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] += 1
#         answer += ans[str(sorted(s.items(), key=lambda x:x[0]))]
#
# print(answer)

ans = {}
answer = 0
for _ in range(N):
    s = "".join(sorted(input()))

    if s not in ans:
        ans[s] = 0

    else:
        ans[s] += 1
        answer += ans[s]

print(answer)
### BUGGY CODE ###

h, n = map(int, input().split())
magics = []
for _ in range(n):
    a, b = map(int, input().split())
    magics.append((a,b))

mins = [None]*(h+1)
mins[0] = 0
ind = 0
while ind < h:
    for a, b in magics:
        target = min(h, ind+a)
        if mins[target] is None:
            mins[target] = b + mins[ind]
        else:
            mins[target] = min(b + mins[ind], mins[target])
    ind += 1
    while True:
        if mins[ind] is not None:
            break
        ind += 1
print(mins[h])


### FIXED CODE ###

h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])
### BUGGY CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]

zzz = ord('-')


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = [zzz for i in range(L+1)]
#x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != zzz and x_idx != T[m]:
        ret = -1
        break

print(ret)

### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0]*(len(s)+1) for _ in range(len(t)+1)]

for i in range(len(t)):
  for j in range(len(s)):
    if t[i] == s[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

i = len(t)
j = len(s)
ans = ''
while i >= 0 and j >= 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    ans = ans + t[i]
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

dp = [[0]*(len(s)+1) for _ in range(len(t)+1)]

for i in range(len(t)):
  for j in range(len(s)):
    if t[i] == s[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

i = len(t)
j = len(s)
ans = ''
while i >= 0 and j >= 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    ans = ans + t[i]
print(ans[::-1])
### BUGGY CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

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

c_d = [0] * n
col_i = [-1] * n
for i in range(n):
    col = c[i] - 1
    c_d[i] = col_i[col]
    col_i[col] = i

for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    ans = r - l + 1
    for j in range(l, r+1):
        if (l <= c_d[j]):
            ans -= 1
    print(ans)


### FIXED CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

N = int(input().split()[0])
a_list = list(map(int, input().split()))
start_w = a_list[0] * 2

# 一番小さいものから決めていく？
for sw in range(start_w + 1):
    w_list = []
    if a_list[0] < sw // 2:
        continue
    w_list.append(sw)
    for i in range(1, N):
        w_list.append((a_list[i - 1] - w_list[i - 1] // 2) * 2)

    if a_list[-1] == (w_list[0] + w_list[-1]) // 2:
        break

ans = " ".join([str(w) for w in w_list])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

N = int(input().split()[0])
a_list = list(map(int, input().split()))

r_list = []
total = 0

for i in range(1, N, 2):
    total += a_list[i]

r_list.append(sum(a_list) - total * 2)

for i in range(1, N):
    r = a_list[i - 1] * 2 - r_list[i - 1]
    r_list.append(r)

ans = " ".join([str(w) for w in r_list])
print(ans)