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

from collections import deque
s = deque(input())
q = int(input())
appendleft=s.appendleft
append=s.append
for i in range(q):
    temp = input().split()
    t = temp[0]
    if t == "1":
        work = deque()
        for el in s:
            work.appendleft(el)
        s.clear()
        for el in work:
            append(el)
    else:
        f = temp[1]
        c = temp[2]
        if f == "1":
            appendleft(c)
        else:
            append(c)
print("".join(list(s)))

### FIXED CODE ###

from collections import deque
def main():
    s = deque(input())
    q = int(input())
    appendleft=s.appendleft
    append=s.append
    flag = False
    for i in range(q):
        temp = input().split()
        if temp[0] == "1":
            flag = not flag
        else:
            if temp[1] == "1":
                if flag:
                    append(temp[2])
                else:
                    appendleft(temp[2])
            else:
                if flag:
                    appendleft(temp[2])
                else:
                    append(temp[2])
    if flag:
        s.reverse()
    print("".join(list(s)))
if __name__=="__main__":
    main()
### BUGGY CODE ###

lst = list(map(int, input().split()))
a_lst = list(map(int, input().split()))
b_lst = list(map(int, input().split()))
c_lst = list(map(int, input().split()))

ab_lst = []
for i in a_lst:
    for j in b_lst:
        ab_lst.append(i+j)
ab_lst = sorted(ab_lst, key = lambda x: -x)[:lst[3]]
abc_lst = []
for i in ab_lst:
    for j in c_lst:
        abc_lst.append(i+j)
for i in sorted(abc_lst, key = lambda x: -x)[:lst[3]]:
    print(i)

### FIXED CODE ###

x,y,z,k = map(int, input().split())
a_lst = sorted(list(map(int, input().split())), reverse=True)
b_lst = sorted(list(map(int, input().split())), reverse=True)
c_lst = sorted(list(map(int, input().split())), reverse=True)

candidate = []
for n in range(x):
    for m in range(y):
        if (n+1)*(m+1) > k:
            break
        else:
            for l in range(z):
                if (n+1)*(m+1)*(l+1) > k:
                    break
                else:
                    candidate.append(a_lst[n]+b_lst[m]+c_lst[l])
for i in sorted(candidate, reverse=True)[:k]:
    print(i)
### BUGGY CODE ###

n=int(input())
s=[str(input()) for _ in range(n)]
l=[s[0]]
for i in range(n):
  if s[i] not in l:
    l.append(s[i])
print(len(l))


### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
t=list(set(s))
print(len(t))
### BUGGY CODE ###

i = int(input())
p = 1
for ii in range(1,i+1):
	p *= ii

print(p % ((10 **9)+7 ))
          

### FIXED CODE ###

i = int(input())
p = 1
M = 10 **9+7 
for ii in range(1,i+1):
	ii %= M
	p *= ii
	p %= M
print(p)
### BUGGY CODE ###

N, M = map(int,input().split())
data = [[list(map(int,input().split())),i] for i in range(M)]

ans = []
for i in range(1,N+1):
    p = [j for j in data if j[0][0]==i]
    if len(p)==0:
        continue
    p.sort(key = lambda x:x[0][1])
    for k in range(len(p)):
         ans.append([p[k][1],str(i).zfill(6) + str(k+1).zfill(6)])

ans.sort(key = lambda x:x[0])

for i in ans:
    print(i[1])

### FIXED CODE ###

N, M = map(int,input().split())
data = [[list(map(int,input().split())),i] for i in range(M)]

data.sort(key = lambda x:x[0][1])

count=[0]*N
ans=[]

for i in data:
    count[i[0][0]-1] += 1
    ans.append([i[1],str(i[0][0]).zfill(6) + str(count[i[0][0]-1]).zfill(6)])

ans.sort(key = lambda x:x[0])

for i in ans:
    print(i[1])
### BUGGY CODE ###

from itertools import accumulate
n=int(input())
A=list(map(int,input().split()))
A=list(accumulate(A))
A=[0]+A
ans=[]
for i in range(n):
  for j in range(i+1,n+1):
    ans.append(A[i]-A[j])
print(ans.count(0))
  

### FIXED CODE ###

from itertools import accumulate
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
A=list(accumulate(A))
A=[0]+A
B=Counter(A)
ans=0
for i in B:
  ans=int(ans+B[i]*(B[i]-1)/2)
print(ans)
### BUGGY CODE ###

import sys
import numpy as np


def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans


N = int(input())
P = np.array(input().split(), np.int32)

print(solve(N, P))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit


def input(): return sys.stdin.readline().rstrip()


@njit
def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans


N = int(input())
P = np.array(input().split(), np.int32)

print(solve(N, P))
### BUGGY CODE ###

from collections import deque
N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D
	test[(L,R)]=D


d=[ -1 for i in range(N+1) ]

def dfs(start):
	V=[ 0 for i in range(N+1) ]
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]


for i,j in test.items():
	x1=i[0]
	x2=i[1]

	if d[x1]==-1:
		dfs(x1)
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"




### FIXED CODE ###

from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D


d=[ None for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]

def dfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]
			else:
				if d[i]-d[v]!=cost[(v,i)]:
					print "No"
					quit()

for i in range(1,N+1):
	if V[i]==0:
		dfs(i)
else:
	print "Yes"
### BUGGY CODE ###

n = int(input())
lis = []
count = 0
for _ in range(n):
    mozi = input()
    if not mozi in lis:
        lis.append(mozi)
        count += 1
print(len(lis))

### FIXED CODE ###

n = int(input())
count = 0
lis = [None]*n
for i in range(n):
    mozi = input()
    lis[i] = mozi
print(len(set(lis)))
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))

dp = np.zeros(shape=N + 1, dtype=np.int64)

for k in range(K):
    for i in range(N):
        dp[max(0, i - A[i])] += 1
        dp[min(N, i + A[i] + 1)] -= 1
    A = dp.cumsum()[:-1]
    if np.all(A >= N):
        break
    dp *= 0

print(' '.join(map(str, A)))


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)

dp = np.zeros(shape=N + 1, dtype=np.int64)

for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0

print(' '.join(map(str, A)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    cost = [INF] * (2 << N)
    used = [False for i in range(M)]
    end = (1 << N) - 1
    
    def dfs(state):
        if state == end:
            return
        for i in range(M):
            ns = state | C[i]
            if not used[i] and state < ns:
                cost[ns] = min(cost[ns], cost[state] + A[i])
                used[i] = True
                dfs(ns)
                used[i] = False
        return cost

    cost[0] = 0
    dfs(0)
    return cost[end] if cost[end] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    # dp[state][i]: i本の鍵[0, i)を使って状態stateにするための最小コスト
    n_states = 1 << N
    end_state = n_states - 1
    dp = [[INF for j in range(2)] for state in range(n_states)]
    dp[0][0] = 0
    dp[0][1] = 0

    for j in range(M):
        m0 = j & 1
        m1 = 1 - m0
        for state in range(n_states):
            next_state = state | C[j]
            dp[state][m1] = min(dp[state][m1], dp[state][m0])
            if next_state > state:
                dp[next_state][m1] = min(dp[next_state][m1], dp[state][m0] + A[j])
    
    m0 = M & 1
    return dp[end_state][m0] if dp[end_state][m0] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))
### BUGGY CODE ###

#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append([])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=putmx(wb,mwb)

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  for j in wmx:
    if not j in bmb[i]:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)



### FIXED CODE ###

#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append({-1})
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].add(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=set(putmx(wb,mwb))

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  if wmx|bmb[i]!=bmb[i]:
    print(mhb+mwb)
    break
else:
  print(mhb+mwb-1)

#print(hmx,wmx,bmb)
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)
a = set()
for i in range(n):
    for j in range(n-i):
        a.add(s[j:j+i+1])
a = sorted(list(a))
print(a[k-1])

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
a = set()
for i in range(5):
    for j in range(n-i):
        a.add(s[j:j+i+1])
a = sorted(list(a))
print(a[k-1])
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
j=0
for i in range(M):
    A[A.index(max(A[:j+1]))]=A[A.index(max(A[:j+1]))]//2
    j=j+1
    if j==300:
        A.sort(reverse=True)    
        j=0
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: x*(-1),list(map(int,input().split()))))
A.sort()
B=[]
for i in range(N):
    heapq.heappush(B,A[i])
for i in range(M):
    heapq.heappush(B,(((heapq.heappop(B))*(-1))//2)*(-1))
print((sum(B))*(-1))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
result = 0
max_height = 0

for i in range(n):
  an = a[i]
  if i == 0:
    max_height = an
    max_height_idx = 0
    continue

  if an >= max_height:
    max_height = an
    max_height_idx = i
    continue

  max_height = max(a[max_height_idx:i])
  result += (max_height - an)

print(result)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
result = 0
max_height = 0

for i in range(n):
  an = a[i]
  if i == 0:
    max_height = an
    max_height_idx = 0
    continue

  if an >= max_height:
    max_height = an
    max_height_idx = i
    continue

  result += (max_height - an)

print(result)
### BUGGY CODE ###

N = int(input())

M = 100000

c = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]


cache = {}

def solve(count, x, l):
    if len(l) == 0:
        return 10000000000

    t = l[0]
    if x // t > 0:
        res = []
        for i in range(x // t + 1):
            if i > 0:
                count += x // (t * i)
                rest = x % (t * i)
                if rest == 0:
                    return count
                res.append(solve(count, rest, l[1:]))
            else:
                res.append(solve(count, x, l[1:]))
        return min(res)
    else:
        return solve(count, x, l[1:])


# for i in range(10):
#     val = 9 ** i
#     if val <= M:
#         print(val)
#         c.append(val)
#
# for i in range(10):
#     val = 6 ** i
#     if val <= M:
#         print(val)
#         c.append(val)

# count = 0
rest = N

result = solve(0, rest, c)
# for i in c:
#     if rest // i > 0:
#         count += rest // i
#         print(str(i) + ', ' + str(rest // i) + ' times, rest = ' + str(rest % i))
#         rest = rest % i
#
#     if rest == 0:
#         break

print(result)


### FIXED CODE ###

# https://atcoder.jp/contests/abc099/tasks/abc099_c

def main():
    max_val = 10**5 + 1
    dp = [i for i in range(max_val)]

    for i in range(max_val):
        p = 1
        while p < max_val:
            dp[i] = min(dp[i], dp[i - p] + 1)
            p *= 6
        p = 1
        while p < max_val:
            dp[i] = min(dp[i], dp[i - p] + 1)
            p *= 9

    N = int(input())
    print(dp[N])


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

n=int(input())
l=sorted(list(map(int,input().split())))
count=0
def nibutan(s,g,num):
  low=s
  high=g-1
  while low<=high:
    mid=(low+high)//2
    num1=l[mid]
    if num>l[-1]:
      return n-1
    elif num<=l[mid] and l[mid-1]<num:
      return mid-1
    elif l[mid-1]>num:
      high=mid-1
    elif l[mid]<num:
      low=mid+1
    else:
      return mid-2
for i in range(n-2):
  for j in range(i+1,n-1):
    if i==n-3 and j==n-2:
      if l[i]+l[j]>l[-1]:
        count+=1
    else:
      num=nibutan(j+1,n,l[i]+l[j])
      count+=num-j
print(count)

### FIXED CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
count=0
for i in range(n-2):
  for j in range(i+1,n-1):
    index=bisect.bisect_left(l,l[i]+l[j])
    count+=index-j-1
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if a[mi-1] >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

N = int(input())
S = input()
dic = {
  "R":[],
  "G":[],
  "B":[]
}
for i in range(N):
  dic[S[i]].append(i)

res = 0
for a in range(len(dic["R"])):
  for b in range(len(dic["G"])):
    for c in range(len(dic["B"])):
      x1 = dic["R"][a]
      x2 = dic["G"][b]
      x3 = dic["B"][c]
      xsum = x1 + x2 + x3
      if xsum%3!=0:
        res += 1
        continue
      ave = int(xsum/3)
      if x1!=ave and x2!=ave and x3!=ave:
        res += 1
        continue
        
print(res)
        

### FIXED CODE ###

N = int(input())
S = input()
C = {"R", "G", "B"}
cumsum = {c:[0 for i in range(N)] for c in C}

for i in range(N):
  s = S[i]
  cumsum[s][i] = 1
for i in range(2, N+1):
  for c in C:
    cumsum[c][-i] = cumsum[c][-i] + cumsum[c][-(i-1)]
#print(cumsum)
ans = 0
for i in range(N-2):
  s = S[i]
  a, b = C - {s}
  ans += cumsum[a][i]*cumsum[b][i]

for i in range(1, (N-1)//2 + 1):
  for j in range(N-2*i):
    #print(j, j+i, j+2*i, S[j]+S[j+i]+S[j+2*i])
    if S[j] != S[j+i] and S[j+i] != S[j+2*i] and S[j] != S[j+2*i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

import bisect
import numpy as np

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

max_idx = np.argmax(np.array(P))
finished = [-1, -1, max_idx, N, N] # index set
#print(finished)

ans = 0
for i in range(N - 1, 0, -1):
    idx = np.where(np.array(P) == i)[0][0]
    idx2 = bisect.bisect_left(finished, idx)
    bisect.insort_left(finished, idx)
    #print(finished)
    x = finished[idx2 - 1]
    y = finished[idx2 + 1]
    z = finished[idx2 + 2]
    w = finished[idx2 - 2]
    #print('When P_i = {}, w={}, x={}, y={}, z={}'.format(i,w,x,y,z))

    C = (x - w) * (y - idx) + (idx - x) * (z - y)
    ans += i * C
    #print('ans = {}'.format(ans))

print(ans)

### FIXED CODE ###

N = int(input())
P = [None] + [int(x) for x in input().split()]
id_list = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    id_list[x] = i

# 左隣にあるインデックスを取得できるようにしておく
# Binary Iindex Treeを使うことで、区間[L,R]内での和をとれば[L,R]内のデータ件数を数えられる
class BIT:
    def __init__(self, n):
        # 要素数を与えてインスタンス化
        self.size = n
        self.tree = [0] * (n + 1) # index must be 1-origin

    def add(self, i, x=1):
        # add x(>= 1) to a_i
        while i <= self.size:
            self.tree[i] += x
            i += i&(-i) # i&(-i) = BITでのi番目の区間の長さ

    def sum(self, i):
        # sum of a_1, a_2, ... , a_i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i) # i&(-i) = BITでのi番目の区間の長さ
        return s

    def search(self, x):
        # 二分探索。a_1 + a_2 + ... + a_i >= xなる最小のインデックスi(>= 1)を返す
        i = 0
        s = 0
        step = 1<<(N.bit_length()-1) # the largest 2^k (= step) <= N
        while step:
            if i+step <= N and s + self.tree[i+step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i+1


def main():
    bit = BIT(N)
    ans = 0
    for x in range(N,0,-1):
        idx = id_list[x]
        L = bit.sum(idx) # 左にある既に書き込んだ数の個数
        bit.add(idx)
        R = N-x-L # 右にある既に書き込んだ数の個数
        ll = bit.search(L-1) if L >= 2 else 0
        l = bit.search(L) if L >= 1 else 0
        r = bit.search(L+2) if R >= 1 else N+1
        rr = bit.search(L+3) if R >= 2 else N+1
        coef = 0
        if l != 0:
            # [b,c]を含むようにする。(a,b) と(c,d)が自由
            coef += (l - ll) * (r - idx)
        if r != 0:
            # [c,d]を含むようにする。
            coef += (rr - r) * (idx - l)
        ans += x * coef
    print(ans)

main()
### BUGGY CODE ###

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

## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A.sort()
duplicatedList = []
while len(A) > 0:
    if A[0] in A:
        kinds += 1
        duplicatedList.append(A.count(A[0]))
        for j in range(A.count(A[0])):
            A.remove(A[0])

if kinds <= K:
    print('0')
elif kinds > K:
    duplicatedList.sort()
    tmp = 0
    for i in range(kinds-K):
        tmp += duplicatedList[i]
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
arr = [[x, y, s-x-y] for x in range(k+1) for y in range(k+1) if k >= s-x-y >= 0]
print(len(arr))

### FIXED CODE ###

k, s = map(int, input().split())
arr = [1 for x in range(k+1) for y in range(k+1) if k >= s-x-y >= 0]
print(sum(arr))
### BUGGY CODE ###

#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            else:
                s += 1
            add(i,1)
            p[ci] = i
            i += 1
        ans[ind] = s-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

    def add(self, i, x=1):
        while i < self.size:
            self.dat[i] += x
            i += i&-i

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()