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

H, N = map(int, input().split())
hpdown = list()
mpdown = list()
for i in range(N):
  a, b = map(int, input().split())
  hpdown.append(a)
  mpdown.append(b)
  
hmax = max(max(mpdown)*2+1, H+max(mpdown)+1)
dp = [10 ** 9] * (hmax)
dp[0] = 0
for h in range(1, hmax):
  for n in range(N):
    if(h-hpdown[n]>=0):
      dp[h] = min(dp[h], dp[h-hpdown[n]] + mpdown[n])
      
ans = 10 ** 9
for i in range(H, hmax):
  if(dp[i] < ans):
    ans = dp[i]
print(ans)

### FIXED CODE ###

H, N = map(int, input().split())
hpdown = list()
mpdown = list()
for i in range(N):
  a, b = map(int, input().split())
  hpdown.append(a)
  mpdown.append(b)
  
hmax = H+(max(hpdown)+1)
dp = [10 ** 9] * (hmax)
dp[0] = 0
for h in range(1, hmax):
  for n in range(N):
    if(h-hpdown[n]>=0):
      dp[h] = min(dp[h], dp[h-hpdown[n]] + mpdown[n])
      
ans = 10 ** 9
for i in range(H, hmax):
  if(dp[i] < ans):
    ans = dp[i]
print(ans)
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
bl=[[]]
for i in range(n-1):
  fr.append([])
  bl.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)
for i in range(k):
  a,b=map(int,input().split())
  bl[a-1].append(b)
  bl[b-1].append(a)

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-len(fr[k-1])-1,end=" ")
      else:
        print(ans-len(fr[k-1])-1)
      break
    else:
      check=use.popleft()
      if not check in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if not x in aldic:
            use.append(x)
        if not check in bl[k-1]:
          ans+=1
for i in range(1,n+1):
  bfs(i)

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])
### BUGGY CODE ###

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

l = 0
num = set()
step = set()
for k in range(1, M + 1):
    while True:
        if l in num:
            l += 1
            l %= N
            continue
        if (l + k) % N not in num:
            break
        if (l + (N - k)) % N not in num:
            l = (l + (N - k)) % N
            break
        l += 1
        l %= N

    print(l + 1, (l + k) % N + 1)
    num.add(l)
    num.add((l + k) % N)


### FIXED CODE ###

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

cnt = 0

l = 0
k = M
while cnt < M and k > 0:
    print(l + 1, l + k + 1)
    cnt += 1
    l += 1
    k -= 2

l = M + 1
k = M - 1
while cnt < M:
    print(l + 1, l + k + 1)
    cnt += 1
    l += 1
    k -= 2
### BUGGY CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * 4000 for _ in range(4000)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

pow2 = [1] * (n + 1)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2 % mod
inv2 = pow_k(2, mod - 2)

dp[0][0] = pow2[n]
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])


### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * 4000 for _ in range(4000)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

inv2 = pow_k(2, mod - 2)
pow2n = pow_k(2, n)

dp[0][0] = pow2n
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

for _ in range(m):
    a[0] = a[0] // 2
    a.sort(reverse=True)


print(sum(a))


### FIXED CODE ###

# priority queueで楽勝だった
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)

for _ in range(m):
    x = -(-a[0] // 2)
    heapq.heapreplace(a, x)
    #print(a)
print(sum(a) * -1)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    t = [-1] * Q
    ans = S
    for i in range(Q):
        query = input()
        if len(query)==1:
            ans = ans[::-1]
        else:
            tmp = list(query.split())
            f = int(tmp[1])
            c = tmp[2]
            ans = c+ans if f==1 else ans+c
            
    print(ans)

main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    rev = False # rev=1で反転した状態
    tail = ""
    head = ""
    for i in range(Q):
        query = input()
        if len(query)==1:
            rev = not rev
        else:
            tmp = list(query.split())
            f = int(tmp[1])
            c = tmp[2]
            if rev:
                if f==1:
                    tail+=c
                else:
                    head=c+head
            else:
                if f==1:
                    head=c+head
                else:
                    tail+=c

    ans = tail[::-1]+S[::-1]+head[::-1] if rev else head+S+tail
    print(ans)

main()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
A = []
L = []

for i  in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        A.append(i+2)
for i in range(Q):
    L=list(map(int,input().split()))
    print(sum(L[0]< x <=L[1] for x in A))


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N,Q = map(int,input().split())
S = input()
A = []
L = []

for i  in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        A.append(i)
        
for i in range(Q):
    L=list(map(int,input().split()))
    minA=bisect_left(A,L[0]-1)
    maxA=bisect_left(A,L[1]-1)
    print(maxA-minA)
### BUGGY CODE ###

N = int(input())
def shiki(a, b, c):
    return a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a

def condition(n):
    count = 0
    i = 0
    j = 0
    z = 1
    while shiki(i, j, z) <= n and n > 5:
        for i in range(1, 50):
            for j in range(1, 50):
                z = 1
                while shiki(i, j, z) <= n and n > 5:
                    if n == shiki(i, j, z):
                        if i == j and j == z and i == z:
                            count += 1
                        else:
                            count += 1
                    z += 1
    print(count)

for i in range(1, N+1):
    condition(i)

### FIXED CODE ###

N = int(input())
ans = [0] * 100000
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

from functools import lru_cache
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  
  if cal(mid-1)<cal(mid+1):
    ans = mid
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

### FIXED CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
note = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)
    note[y].append(x)

len_list = []
visited_list = []
def visited(p):
    for e in visited_list:
        if e == p:
            return True
    return False
def dfs(p, length = 0):
    # 訪問済みならlength-1をメモ
    if visited(p) is True:
        len_list.append(length-1)
    # 訪問の印を付ける
    visited_list.append(p)
    # 行き場所がなければlengthをメモ
    if info[p] == []:
        len_list.append(length)
    for d in info[p]:
        dfs(d, length + 1)
for i in range(1,N+1):
    if note[i] != []:
        continue
    dfs(i)
    visited_list.clear()
ans = max(len_list)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())
ad = [[] for i in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    ad[x].append(y)

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)
### BUGGY CODE ###

import copy
def aaa(n,m):
    count1 = 1
    count2 = 1
    l1 = [0]*n
    l2 = [0]*m
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l1.append(count1)
    l1.append(count2)
    l1 = l1 + l2
    return l1
s = list(input())
j = 0
a = 0
b = 0
l = []
for i in range(len(s)):
    if s[i] == "R" and j == 0:
        a = a + 1
    elif s[i] == "R" and j == 1:
        p = copy.copy(a-1)
        q = copy.copy(b-1)
        l = l + aaa(p,q)
        a = 1
        b = 0
        j = 0
    else:
        b = b + 1
        j = 1
l = l + aaa(a-1,b-1)
for x in l:
    print(x,end=" ")

### FIXED CODE ###

def aaa(n,m):
    count1 = 1
    count2 = 1
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l3 = [count1,count2]
    return l3
s = list(input())
n = len(s)
j = 0
a = 0
b = 0
l = [0]*n
for i in range(len(s)):
    if s[i] == "R" and j == 0:
        a = a + 1
    elif s[i] == "R" and j == 1:
        l[c-1] = aaa(a-1,b)[0]
        l[c] = aaa(a-1,b)[1]
        a = 1
        b = 0
        j = 0
    elif s[i] == "L" and j == 0:
        j = 1
        c = i
    elif s[i] == "L" and j == 1:
        b = b + 1
l[c-1] = aaa(a-1,b)[0]
l[c] = aaa(a-1,b)[1]
for x in l:
    print(x,end=" ")
### BUGGY CODE ###

N, M = map(int, input().split())
p = list()
y = list()
d = dict()
for i in range(M):
    inp_p, inp_y = map(int, input().split())
    p.append(inp_p)
    y.append(inp_y)
    if inp_p in d:
        d[inp_p].append(inp_y)
    else:
        d[inp_p] = [inp_y]
for i in d:
    d[i] = sorted(d[i])
for i, j in zip(p, y):
    print("{:06d}{:06d}".format(i, d[i].index(j)+1))

### FIXED CODE ###

N, M = map(int, input().split())
p = [[] for i in range(M)]
counter = [0] * N
ans = [""] * M

for i in range(M):
    k, y = map(int, input().split())
    p[i] = [k, y, i]

p.sort(key=lambda x:x[1])
for k, y, i in p:
    counter[k-1] += 1
    ans[i] = "{:06d}{:06d}".format(k, counter[k-1])

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q = deque([(x1,y1,0,(0,0),0)])
dx = [0,1,0,-1]
dy = [1,0,-1,0]
dist = [[float("inf")]*w for _ in range(h)]
dist[x1][y1] = 0
while q:
    x, y, d, t, td = q.popleft()
    for xx, yy in zip(dx,dy):
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
        else:
            nd = d+1
            ntd = 1
        if nd<=dist[nx][ny]:
            q.append((nx,ny,nd,(xx,yy),ntd))
            dist[nx][ny] = nd
if dist[x2][y2] >10**10:
    print(-1)
else:
    print(dist[x2][y2])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: int(x)-1, input().split())
s = [None]*h
for i in range(h):
    s[i] = input()
    
from queue import deque
q0 = deque([(0,x1,y1,(0,0),0)])
q1 = deque()

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# dist = [[None]*w for _ in range(h)]
dist = [None]*(w*h)
dist[x1*w+y1] = 0
# done = [[0]*w for _ in range(h)]
done = [0]*(w*h)
done[x1*w+y1] = 15

while q0 or q1:
    if not q0:
        q0 = q1
        q1 = deque()
    d, x, y, t, td = q0.popleft()
    for i,(xx, yy) in enumerate(zip(dx,dy)):
        if (-xx,-yy)==t:
            continue
        nx, ny = xx+x, yy+y
        if nx<0 or nx>=h or ny<0 or ny>=w or s[nx][ny]=="@":
            continue
        if (xx,yy)==t and td<k:
            nd = d
            ntd = td+1
            q = q0
        else:
            nd = d+1
            ntd = 1
            q = q1
        if dist[nx*w+ny] is None or nd<dist[nx*w+ny]:
            q.append((nd,nx,ny,(xx,yy),ntd))
            dist[nx*w+ny] = nd
            done[nx*w+ny] = 1<<(i)
        elif nd==dist[nx*w+ny]and ((done[nx*w+ny]&1<<(i))==0):
            q.append((nd,nx,ny,(xx,yy),ntd))
            done[nx*w+ny] |= 1<<(i)
            
if dist[x2*w+y2] is None:
    print(-1)
else:
    print(dist[x2*w+y2])
### BUGGY CODE ###

from scipy.sparse import*
g=[]
n=int(raw_input())
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g+=[(a-1,b-1,1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g+=[(n,a-1,b)]
	z[a-1]=b
a,b,c=zip(*g)
a=map(int,csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,n))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		exit()
for e in g:
	if e[0]<e[1] and abs(a[e[0]]-a[e[1]])!=1:
		print('No')
		exit()
print('Yes')
print("\n".join(map(str,a[:n])))

### FIXED CODE ###

#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))
### BUGGY CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

    P = 10**9 + 7
    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += base*bai
        ans %= mod
        p *= 25
        q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
    print(ans)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    #q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*z[l+k-i]*bai
        ans %= mod
        p *= 25
        p %= mod
        #q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		for k in range(l):
			if a[i+k]!=P[k]:
				break
		else:c+=1
	print c
	

### FIXED CODE ###

while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]==P:c+=1
	print c
### BUGGY CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    lim = max(a)
    amount = [0]*lim
    for i in range(lim):
        amount[i] = a.count(i+1)
        ans += amount[i]*(amount[i]-1)//2
    #print(ans)
    for j in range(n):
        ansout = ans
        #print(amount[a[j]-1])
        ansout -= amount[a[j]-1] -1
        print(ansout)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
def main():
    from collections import Counter
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    c = Counter(a)
    for i in range(n):
        ans += c[i+1]*(c[i+1]-1)//2
    for j in range(n):
        print(ans - c[a[j]] + 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
memo = []
for i in range(n):
    m = int(input())
    if m in memo: memo.pop(memo.index(m))
    else: memo.append(m)
print(len(memo))

### FIXED CODE ###

memo = set()
for i in range(int(input())):
    a = input()
    if a in memo: memo.remove(a)
    else: memo.add(a)
print(len(memo))
### BUGGY CODE ###

S = input()
B = []
Nc = 0
Ns = 0
for i in range(len(S)):
    if S[i] == 'W':
        B.append(1)
    if S[i] == 'B':
        B.append(0)

while B != [1]*len(B) and B != [0]*len(B):
    if B.index(0) > B.index(1):
        B = [1] + B
        B[0:B.index(0)+1] = [0]*(B.index(0)+1)
        Nc += 1
    else:
        B = [0] + B
        B[0:B.index(1)+1] = [1]*(B.index(1)+1)
        Nc += 1
print(Nc)

### FIXED CODE ###

S = input()
B = []
Nc = 0

for i in range(len(S)-1):
    if S[i] != S[i+1]:
        Nc += 1
print(Nc)
### BUGGY CODE ###

n,k=map(int,input().split())
pi=list(map(int,input().split()))

pmax=0
for i in range(n-k+1):
    psum=sum(pi[i:i+k])
    if psum>pmax:
        pmax=psum
px=(k+pmax)/2
print(px)   

### FIXED CODE ###

n,k=map(int,input().split())
pi=list(map(int,input().split()))

pmax=sum(pi[0:k])
#print(pmax)
psum=pmax
for i in range(1,n-k+1):
    psum=psum-pi[i-1]+pi[i+k-1]
#    print(i,k,psum)
    if psum>pmax:
        pmax=psum
px=(k+pmax)/2
print(px)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from bisect import bisect

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    C = [next(it) for i in range(N)]
    D = list(zip(it, it, range(Q)))

    D.sort(key=lambda x: (x[1], x[0]), reverse=True)

    C1 = [[-1, []] for i in range(N)]
    rx = D[0][1]
    for i, ci in zip(range(rx), C):
        x = C1[ci-1]
        x[1].append(x[0])
        x[0] = i
    C2 = C1[:]
    C2.sort()

    ans = [0] * Q
    rj = rx
    for li, ri, i in D:
        if ri < rj:
            for j in reversed(range(ri, rj)):
                cj = C[j] - 1
                x = C1[cj]
                x[0] = x[1].pop()
            C2.sort()
            rj = ri

        k = bisect(C2, [li-1,])
        ans[i] = N - k

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()