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

N = int(raw_input())
lis = []
for i in xrange(N):
	num = int(raw_input())
	if not lis:
		lis.append(num)
	else:
		for j in xrange(len(lis)):
			if lis[j] == num:
				lis.pop(j)
				break
			elif lis[j] > num:
				lis.insert(j,num)
				break
		else:
			lis.append(num)
print len(lis)

### FIXED CODE ###

from collections import Counter
N = int(raw_input())
lis = []
for i in xrange(N):
	lis.append(int(raw_input()))
lis.sort()
lister = dict(Counter(lis)).items()
count = 0
for item in lister:
	if item[1] % 2 == 1:
		count += 1
print count
### BUGGY CODE ###

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

cost = [0 for _ in range(len(h))]

for i in range(len(h)):
    if i == 0:
        continue
    if i == 1:
        cost[i] = abs(h[i] - h[i - 1])
    else:
        cost[i] = min(cost[i - 1 - k] + abs(h[i] - h[i - 1 - k]) for k in range(min(i, k)))
print(cost[i])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
 
cost = [0 for _ in range(len(h))]
 
for i in range(len(h)):
    if i == 0:
        continue
    if i == 1:
        cost[i] = abs(h[i] - h[i - 1])
    else:
        cost[i] = min(cost[i - 1 - k] + abs(h[i] - h[i - 1 - k]) for k in range(min(i, k)))
print(cost[i])
### BUGGY CODE ###

def solve(s1, s2, s3, S):
	flag = 0
	for i in range(len(S)):
		if flag == 0:
			if S[i] == s1:
				flag = 1
		elif flag == 1:
			if S[i] == s2:
				flag = 2
		elif flag == 2:
			if S[i] == s3:
				flag = 3
	if flag == 3:
		return True
	else:
		return False

if __name__ == "__main__":
	N = int(input())
	S = input()
	ans = 0
	for s1 in range(0, 10):
		for s2 in range(0, 10):
			for s3 in range(0, 10):
				if solve(str(s1), str(s2), str(s3), S):
					ans += 1
	print(ans)

### FIXED CODE ###

import itertools

N = int(input())
S = input()
S = [int(x) for x in S]

left_index = [[-1] * (N+1) for _ in range(10)]

for i,x in enumerate(S,1):
	for j in range(10):
		left_index[j][i] = left_index[j][i-1]
	left_index[x][i] = i


answer = 0
for a,b,c in itertools.product(range(10),repeat=3):
	i = N
	bl = True
	for x in [a,b,c]:
		i = left_index[x][i] - 1
		if i < -1:
			bl = False
			break
	if bl:
		answer += 1

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

import sys,bisect
input=sys.stdin.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]
for i in range(int(input())):
    v,L=map(int,input().split())
    if 2**9>v:
        print(dp[v][L])
    else:
        t=[]
        while v>=2**9:
            t.append(vw[v])
            v//=2
        n=len(t)
        temp[0][0]=0
        temp[0][1]=0
        for i in range(1,2**n):
            m=i.bit_length()
            temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
            temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
        ans=0
        for i in range(2**n):
            if L>=temp[i][1]:
                ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]])
        print(ans)

### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

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

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

#memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
#    if (a, b, c, i) in memo:
#        return memo[(a, b, c, i)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

#    memo[(a, b, c, i)] = ret
    return ret

print(dfs(0, 0, 0, 0))

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

mod=10**9+7

def calc(mat1,mat2):
  n=len(mat1)
  ret=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        ret[i][j]+=mat1[i][k]*mat2[k][j]
        ret[i][j]%=mod
  return ret

n,k=map(int,input().split())
tmp=[[0]*n for _ in range(n)]
for i in range(n):
  tmp[i][i]=1
matrix=[list(map(int,input().split())) for _ in range(n)]
for i in range(60):
  if k&(1<<i):
    tmp=calc(tmp,matrix)
  matrix=calc(matrix,matrix)  
ans=0
for i in range(n):
  for j in range(n):
    ans+=tmp[i][j]
    ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7

def calc(mat1,mat2):
  n=len(mat1)
  ret=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        ret[i][j]+=mat1[i][k]*mat2[k][j]
        ret[i][j]%=mod
  return ret

n,k=map(int,input().split())
tmp=[[0]*n for _ in range(n)]
for i in range(n):
  tmp[i][i]=1
matrix=[list(map(int,input().split())) for _ in range(n)]
for i in range(60):
  if k&(1<<i):
    tmp=calc(tmp,matrix)
  matrix=calc(matrix,matrix)  
ans=0
for i in range(n):
  for j in range(n):
    ans+=tmp[i][j]
    ans%=mod
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    Ans = 0
    for i in range(len(A)-1):
        C = 0
        for j in range(i+1, len(A)):
            C += A[j] % (10**9 + 7)
        Ans += (A[i]*C) % (10**9 + 7)
    print(Ans % (10**9 + 7))
    
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    Ans = 0
    C = 0
    for i in range(1, len(A)):
        C += A[i-1]
        Ans += A[i]*C % (10**9+7)
    print(Ans % (10**9 + 7))
    
resolve()
### BUGGY CODE ###

k,s = list(map(int,input().split()))


ans = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        ans += 1
        
print(ans)


### FIXED CODE ###

k,s = list(map(int,input().split()))

def fact(n):
  return sum([x for x in range(1,n+1)])

ans = 0
r = 0
for x in range(k+1):
  for y in range(x,k+1):
    if 0 <= s - (x+y) <= k:
      if (x==y):
          ans += 1
      else:
          ans += 2

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

n = int(input())
s = []
for _ in range(n):
    s.append(input())

def allequal(s):
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[0][0]:
                return False
    return True

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def val(s):
    global n
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[j][i]:
                return False
    return True

if allequal(s):
    print(n**2)
else:
    res = 0
    for k in range(0,n):
        if val(plusa(s,k)):
            res += n
    print(res)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
st=list(map(''.join,zip(*s)))

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

res = 0
for i in range(n):
    if plusa(st,i) == plusb(s,i):
        res += n

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

from collections import deque

n, m = map(int, input().split(" "))
load = {}
for _ in range(m):
    a, b = map(int, input().split(" "))
    load[a] = load.get(a, set()) | set({b})
    load[b] = load.get(b, set()) | set({a})

queue = deque([1])
visited = {1: 1}

while len(queue) != 0:
    curr = queue.popleft()
    for _next in load[curr]:
        if visited.get(_next, -1) == -1:
            visited[_next] = curr
            queue.append(_next)

if len(visited) == n:
    print("Yes")
    for i in range(2, n+1):
        print(visited[i])
else:
    print("No")

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split(" "))
load = {i:[] for i in range(1, n+1)}
for _ in range(m):
    a, b = map(int, input().split(" "))
    load[a].append(b)
    load[b].append(a)

queue = deque([1])
visited = {1: 1}

while len(queue) != 0:
    curr = queue.popleft()
    for _next in load[curr]:
        if visited.get(_next, -1) == -1:
            visited[_next] = curr
            queue.append(_next)

if len(visited) == n:
    print("Yes")
    for i in range(2, n+1):
        print(visited[i])
else:
    print("No")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p=[]
cnt=[]
zero=0
for i in range(n):
	if a[i]==0:
		zero+=1
	elif a[i] not in p:
		p.append(a[i])
		cnt.append(1)
	else:
		for j in range(len(p)):
			if a[i]==p[j]:
				cnt[j]+=1
if len(p)==3:
	if cnt[0]==cnt[1]==cnt[2]==n/3:
		if p[0]^p[1]^p[2]==0:
			print("Yes")
			exit()
elif len(p)==1:
	if cnt[0]==n/3*2:
		print("Yes")
		exit()
elif len(p)==0:
	if sum(a)==0:
		print("Yes")
		exit()
print("No")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=[]
cnt=[]
zero=0
for i in range(n):
	if len(p)>=4:
		print("No")
		exit()
	if a[i]==0:
		zero+=1
	elif a[i] not in p:
		p.append(a[i])
		cnt.append(1)
	else:
		for j in range(len(p)):
			if a[i]==p[j]:
				cnt[j]+=1
if n%3!=0 and zero!=n:
	print("No")
	exit()
if len(p)>=4:
	print("No")
	exit()
if len(p)==3:
	if cnt[0]==cnt[1]==cnt[2]==n/3:
		if p[0]^p[1]^p[2]==0:
			print("Yes")
			exit()
	else:
		print("No")
		exit()
elif len(p)==1:
	if cnt[0]==n/3*2:
		print("Yes")
		exit()
elif len(p)==0:
	if sum(a)==0:
		print("Yes")
		exit()
print("No")
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())

maze=[list(input()) for i in range(h)]

ans=0

dx=[1,-1,0,0]
dy=[0,0,1,-1]


for i in range(h):
  for j in range(w):
    for ii in range(h):
      for jj in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='#' or maze[ii][jj]=='#':
          continue

        dp=[[-1]*w for i in range(h)]

        while Q:
          p=Q.popleft()
          if p[0]==ii and p[1]==jj:
            ans=max(ans,p[2])
            break
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==-1:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=p[2]+1


print(ans)

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())

maze=[list(input()) for i in range(h)]

ans=0

dx=[1,-1,0,0]
dy=[0,0,1,-1]


for i in range(h):
  for j in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='#':
          continue

        dp=[[-1]*w for i in range(h)]

        dp[i][j]=0

        while Q:
          p=Q.popleft()
          ans=max(ans,p[2])
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==-1:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=p[2]+1


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

def binary_search(target, left, right, nums):
    if(left > right):
        return -1
    mid = (right-left)//2 + left
    if(nums[mid] == target):
        return mid
    elif(nums[mid] < target):
        return binary_search(target, mid+1, right, nums)
    else:
        return binary_search(target, left, mid-1, nums)
def Main(N, S):
    ans = 0
    d = {'R':[], 'G':[], 'B':[]}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    lenb = len(d['B'])
    for i in d['R']:
        for j in d['G']:
            sub = 0
            lenb = len(d['B'])
            di = abs(i-j)
            mi = min(i,j)
            ma = max(i,j)
            a = mi-di
            b = ma+di
            x = binary_search(a, 0, lenb-1, d['B'])
            y = binary_search(b, 0, lenb-1, d['B'])
            if x>=0 and y>=0:
                sub = 2
            elif x>=0 or y>=0: 
                sub = 1
            ci = (i+j)//2
            cf = (i+j)/2
            if ci == cf:
                z = binary_search(ci, 0, lenb-1, d['B'])
                if z>=0:
                    sub += 1
            ans += lenb - sub
    return ans
        
    

def main():
    N = int(input())
    S = str(input())
    print(Main(N,S))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
def Main(N, S):
    num = [0]*3
    for c in S:
        if c == 'R':
            num[0] += 1
        elif c == 'G':
            num[1] += 1
        else:
            num[2] += 1
    ans = np.prod(num)
    sub = 0
    i = 0
    j = 1
    while(i-2 < N):
        while(i+2*j < N):
            a = i
            b = i+j
            c = i+2*j
            if S[a] != S[b] and S[a] != S[c] and S[b] != S[c]:
                sub += 1
            j += 1
        i += 1
        j = 1
    return ans - sub
        
    

def main():
    N = int(input())
    S = str(input())
    print(Main(N,S))

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

from sys import stdin
from random import randint
from time import time
input = lambda: stdin.readline().rstrip()
start = time()
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.reverse()
ok = 0
t = time() - start
while t < 1.9:
    cnt = 0
    for i in range(n):
        if a[i] == b[i]:
            rng = randint(0, n - 1)
            b[i], b[rng] = b[rng], b[i]
            cnt += 1
    if cnt == 0:
        ok = 1
        break
    t = time() - start
if ok == 1:
    print("Yes")
    print(*b)
else:
    print("No")


### FIXED CODE ###

from sys import stdin
from random import randint
from time import time
input = lambda: stdin.readline().rstrip()
start = time()
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.reverse()
ok = 0
t = time() - start
while t < 1.8:
    cnt = 0
    for i in range(n):
        if a[i] == b[i]:
            rng = randint(0, n - 1)
            b[i], b[rng] = b[rng], b[i]
            cnt += 1
    if cnt == 0:
        ok = 1
        break
    t = time() - start
if ok == 1:
    print("Yes")
    print(*b)
else:
    print("No")
### BUGGY CODE ###

import numpy as np
from copy import deepcopy
def draft(A, K, N):
    A = np.array(A)
    K = min(K, 50)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N+1, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        A = np.cumsum(tmp)[:-1]
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

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

def resolve():
    import numpy as np
    h, n = map(int, input().split())
    lab = np.zeros((n, 2), dtype=np.int)
    i = 0
    while True:
        try:
            a, b = map(int, input().split())
            lab[i][0] = a
            lab[i][1] = b
        except:
            break
        i += 1
    ma = np.max(lab[:, 0])
    dp = np.ones((n + 1, h + ma), dtype=np.int) * np.inf
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + ma):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j >= lab[i][0]:
                dp[i+1][j] = min(dp[i+1][j-lab[i][0]] + lab[i][1], dp[i+1][j])
    print(np.int(np.min(dp[n, h:])))
resolve()

### FIXED CODE ###

def resolve():
    h, n = map(int, input().split())
    lab = []
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
        except:
            break
    cost = [0] * (h+1)
    for i in range(1, h+1):
        mb = 10 ** 8
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][1])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return dp[i][j][k]

print(rec(susicount[2],susicount[1],susicount[0]))

### FIXED CODE ###

# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      if i>0:
        dp[i][j][k] += i * dp[i-1][j+1][k]
      if j>0:
        dp[i][j][k] += j * dp[i][j-1][k+1]
      if k>0:
        dp[i][j][k] += k * dp[i][j][k-1]
      dp[i][j][k] += N
      dp[i][j][k] /= (i+j+k)

print(dp[sushi[2]][sushi[1]][sushi[0]])
### BUGGY CODE ###

from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


N, Q = map(int, input().split())
*c, = map(int, input().split())
tree = SegTree(N+1, 0, add)
m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
m.sort(key=lambda x:x[1])

right = 0
pos = [-1]*(N+1)
ans = [0]*(Q)

for l, r, k in m:
    if right!=r:
        for i in range(right, r):
            if pos[c[i]] != -1:
                tree.update(pos[c[i]], 0)
            pos[c[i]] = i+1
            tree.update(i+1, 1)
    ans[k] = tree.get(l, r+1)
    right = r

for i in ans:
    print(i)


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

n = int(input())
l = []
cnt = 0
for i in range(n):
    s = input()
    if s not in l:
        cnt += 1
        l.append(s)
print(cnt)

### FIXED CODE ###

n = int(input())
l = {}
for i in range(n):
    s = input()
    l[s] = 1
print(len(l))