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

N = int(input())
A = list(map(int, input().split()))
M = [0] * 4
for a in A:
    M[a] += 1
dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(M[3]+1):
    for j in range(M[3]+M[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print("{:.10f}".format(dp[M[1]][M[2]][M[3]]))

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(C[3]+1):
    for j in range(C[3]+C[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(nums):
    return reduce(fractions.gcd, nums)

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

maxgcd = 0
for i in range(len(a)):
    temp = gcd(a[:i] + a[i + 1:])
    if temp > maxgcd:
        maxgcd = temp

print(maxgcd)

### FIXED CODE ###

from fractions import gcd

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

lgcd, rgcd = [], []
for i in range(n):
    if i == 0:
        lgcd.append(a[0])
        rgcd.append(a[n-1])
        continue

    lgcd.append(gcd(lgcd[i-1], a[i]))
    rgcd.append(gcd(rgcd[i-1], a[-1-i]))

maxgcd = 1
for i in range(n):
    if i == 0:
        tempgcd = rgcd[n-2]
    elif i == n-1:
        tempgcd = lgcd[n-2]
    else:
        tempgcd = gcd(lgcd[i-1], rgcd[n-2-i])
    maxgcd = max(maxgcd, tempgcd)
print(maxgcd)
### BUGGY CODE ###

def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        append = cdp.append
        for bit in range(1, 2**n):
            v, w = 0, 0
            for j in range(n):
                if 2**j & bit:
                    v += ca[j][0]
                    w += ca[j][1]
            if w <= W:
                cdp[bit] = (w, v)
        cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect_right


def meet_in_the_middle(a: list, limit: int) -> tuple:
    first_v, first_w, second_v, second_w = [], [], [], []
    for items, v_append, w_append in (
            (a[:len(a)//2], first_v.append, first_w.append),
            (a[len(a)//2:], second_v.append, second_w.append)
    ):
        enumerated = [(0, 0)]
        for v, w in items:
            enumerated += [(w+_w, v+_v) for _w, _v in enumerated]

        enumerated.sort()
        enumerated = enumerated[:bisect_right(enumerated, (limit, float("inf")))] + [(limit+1, 0)]
        max_v = -1
        for (cw, cv), (nw, nv) in zip(enumerated, enumerated[1:]):
            if cw < nw and max_v < cv:
                v_append(cv)
                w_append(cw)
                max_v = cv

    return (first_v, first_w), (second_v, second_w)


N, W = map(int, input().split())
a = [list(map(int, l.split())) for l in sys.stdin]

(first_v, first_w), (second_v, second_w) = meet_in_the_middle(a, W)
ans = 0
for v, w in zip(first_v, first_w):
    i = bisect_right(second_w, W-w)-1
    new_v = v + second_v[i]
    if ans < new_v:
        ans = new_v
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
MOD = 998244353

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()

for i in range(n):
    idx = i + lr
    dp2[idx] += dp[i]
    dp2 %= MOD
    dp = dp2

print(dp[n - 1])

### FIXED CODE ###

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

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

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)
### BUGGY CODE ###

def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [False]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.pop()
            for nex,d in e[now]:
                if dis[nex] == False:
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == False:
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append((x,0))
        while q:
            now,cnt = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = cnt+d
                    q.append((nex,cnt+d))
                else:
                    if dis[nex] != cnt+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

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

import sys
import time
def anscheck(x,y,d,e,f):
    # print "%.3f %.3f %.3f %.3f %.3f"%(x,y,d,e,f)
    if d*x+e*y == f:
        # print "correct!"
        print "%.3f %.3f"%(x,y)
        return True
    else:
        # print "different"
        return False
for line in sys.stdin:
    a,b,c,d,e,f = map(float,line.split())
    i=1
    while True:
        if (a*i-c) % b ==0:
            x=i
            if a*i-c>0:
                y= -((a*i-c)/b)
            elif a*i-c<0:
                y= (a*i-c)/b
            else:
                pass
            if anscheck(x,y,d,e,f):
                break
        # if b*i-c % a == 0:
        #     x=i
        #     if b*i>c:
        #         y= -(b*i-c)/a
        #     elif b*i<c:
        #         y= (b*i-c)/a
        #     else:
        #         pass
        #     anscheck(x,y,d,e,f)
        if (a*(-i)-c) % b ==0:
            x=-i
            if a*(-i)-c>0:
                y= (a*(-i)-c)/b
            elif a*(-i)-c<0:
                y= -((a*(-i)-c)/b)
            else:
                pass
            if anscheck(x,y,d,e,f):
                break
        # if b*(-i)-c % a ==0:
        #     x=-i
        #     if b*(-i)>c:
        #         y= -(b*(-i)-c)/a
        #     elif b*(-i)<c:
        #         y= (b*(-i)-c)/a
        #     else:
        #         pass
        #     anscheck(x,y,d,e,f)
        i+=1.0

### FIXED CODE ###

import sys
import time
#1.2 2.8 4.12 1.5 3.0 4.5
for line in sys.stdin:
    a1,b1,c1,a2,b2,c2 = map(float,line.split())
    i=0
    x = (c1*b2-c2*b1) / (a1*b2-a2*b1)
    y = (a1*c2-a2*c1) / (a1*b2-a2*b1)
    if "-0" in str(x):
        x = 0.0
    print "%.3f %.3f"%(x,y)
### BUGGY CODE ###

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

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0, -1)
print(*ans)

### FIXED CODE ###

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

def dfs(v, p, tree, ans):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v, tree, ans)

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    dfs(0, -1, tree, ans)

    print(*ans)

main()
### BUGGY CODE ###

import itertools
import fractions
from functools import reduce


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


k = int(input())
n = []
for i in range(1, k+1):
    n.append(i)
res = 0
for v in itertools.product(n, repeat=3):
    res += gcd(v[0], v[1], v[2])
print(res)


### FIXED CODE ###

from math import gcd
k = int(input())
res = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        t = gcd(a,b)
        for c in range(1,k+1):
            res += gcd(t,c)
print(res)
### BUGGY CODE ###

N,M=input().split()
N,M=int(N),int(M)
A=input().split()
A=[int(n) for n in A]

A.sort(reverse=True)

for i in range(M):
    a=A[0]//2
    del A[0]
    flag=True
    for j in range(N-1):
        #print(A,a,A[j])
        if A[j]<a:
            A.insert(j,a)
            #print('inserted',A)
            flag=False
            break
    if flag:
        A.insert(N-1,a)
        #print('inserted',A)

sum=0
for i in range(N):
    sum+=A[i]
print(sum)


### FIXED CODE ###

import heapq

N,M=input().split()
N,M=int(N),int(M)
A=input().split()
A=[-int(n) for n in A]

heapq.heapify(A)

for i in range(M):
    a=((-1*heapq.heappop(A))//2)*(-1)
    heapq.heappush(A,a)
sum=0
for i in range(N):
    sum+=A[i]
print(-sum)
### BUGGY CODE ###

S=input()
Q=int(input())

for i in range(Q):
  a=input().split()
  if a[0]=="1":
    S=S[::-1]
  else:
    if a[1]=="1":
      S="".join([a[2],S])
    else:
      S="".join([S,a[2]])
      
print(S)

### FIXED CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
flag=False

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    if flag:
      flag=False
    else:
      flag=True
  else:
    if s[2]=="1":
      if flag:
        d.append(s[4])
      else:
        d.appendleft(s[4])
    else:
      if flag:
        d.appendleft(s[4])
      else:
        d.append(s[4])
      
if flag:
  d.reverse()
  
print("".join(d))
### BUGGY CODE ###

K = int(input())

flags = [-1] * (10**8+7)

count = 0
now = 1
flags[0] = 1
while count != K:
    if now < 10:
        flags[now] = 1
    elif now < 100:
         if abs((now % 10) - (now // 10)) <= 1:
             flags[now] = 1
         else:
             flags[now] = 0
    else:
        n = int(str(now)[1:])
        if len(str(now)[1:]) != len(str(n)):
            if int(str(n)[0]) == 1 or int(str(n)[0]) == 0:
                if flags[n]:
                    if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                        flags[now] = 1
                    else:
                        flags[now] = 0
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
        else:
            if flags[n]:
                if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                    flags[now] = 1
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
    if flags[now] == 1:
        count += 1
        # print(now)
    # print('count: {}, now: {}, flag: {}'.format(count, now, flags[now]))
    now += 1

print(now - 1)


### FIXED CODE ###

from collections import deque

K = int(input())

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

x = 1
count = 0
while K != count:
    x = queue.popleft()
    if (x % 10) != 0:
        queue.append(10 * x + (x % 10) - 1)
    queue.append(10 * x + (x % 10))
    if (x % 10) != 9:
        queue.append(10 * x + (x % 10) + 1)
    count += 1
print(x)
### BUGGY CODE ###

#coding: utf-8

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

count = 0
for i, a in enumerate(A):
    for offset in range(N - i):
        if (a + A[i + offset]) == offset:
            count += 1
print(count)


### FIXED CODE ###

#coding: utf-8

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

L = {}
for i, a in enumerate(A):
    k = i + a
    if k not in L:
        L[k] = 1
    else:
        L[k] += 1

count = 0
for j, a in enumerate(A):
    k = j - a
    if k in L:
        count += L[k]
print(count)
### BUGGY CODE ###

n = int(input())
c = input()
ans = 0

while c.find('WR') != -1:
    leftW = c.find('W')
    rightR = c.rfind('R')
    c = c[leftW+1:rightR]
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
c = input()

w = 0
r = c.count('R')
i = 0
ans = max(w, r)
while i <= n - 1:
    if c[i] == 'W':
        w += 1
    else:
        r -= 1
    ans = min(ans, max(w, r))
    i += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
from decimal import Decimal

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

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = heappop(a)/2
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

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

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = (-1)*heappop(a)//2*(-1)
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))
### BUGGY CODE ###

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

import sys
import os

def is_prime(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3,int(n**0.5)+1,2):   # only odd numbers
        if n%i==0:
            return False
    return True

def make_primes():
    primes = [2]
    i = 3
    while True:
        if is_prime(i):
            primes.append(i)
            if len(primes) > 105000:
                break
        i += 2
    return primes

primes = make_primes()
for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    subset = primes[:n]
    print(sum(subset))

### FIXED CODE ###

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

import sys
import os

def is_prime_list():
    N = 105000
    lst = [True] * N
    lst[0] = False
    lst[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if lst[i] == True:
            for j in range(2, N):
                index = i * j
                if index < N:
                    lst[i * j] = False
    return [i for i in range(2, N) if lst[i]]


primes = is_prime_list()
for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    subset = primes[:n]
    print(sum(subset))
### BUGGY CODE ###

n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
dp =  [[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j - v[i][0] >= 0:
            if dp[i][j-v[i][0]] + v[i][1] > dp[i][j]:
                dp[i+1][j] = dp[i][j-v[i][0]] + v[i][1]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

### FIXED CODE ###

n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
dp =  [[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j - v[i][0] >= 0:
            if dp[i][j-v[i][0]] + v[i][1] > dp[i][j]:
                dp[i+1][j] = dp[i][j-v[i][0]] + v[i][1]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])
### BUGGY CODE ###

n, m = map(int, input().split(' '))
submits = [input().split() for i in range(m)]

WA_nums = dict()
AC = []
penalty = 0
for submit in submits:
    p, s = submit
    if s == 'AC':
        if p in AC:
            continue
        if p in WA_nums:
            penalty += WA_nums[p]
        AC.append(p)
    else:
        if p in WA_nums:
            WA_nums[p] += 1
        else:
            WA_nums[p] = 1

print(len(AC), penalty)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split(' '))

WAs = [0] * n
correct = 0
penalty = 0
for i in range(m):
    p, s = input().strip().split(' ')
    p = int(p) - 1
    if WAs[p] == -1:
        continue
    if s == 'AC':
        penalty += WAs[p]
        correct += 1
        WAs[p] = -1
    else:
        WAs[p] += 1

print(correct, penalty)
### BUGGY CODE ###

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

count = 0
for x in range(k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if x + y + z == s:
                if x == y == z:
                    count +=1
                elif x == y or y==z:
                    count +=3
                else:
                    count +=6
print(count)

### FIXED CODE ###

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

count = 0
for x in range(k+1):
    for y in range(k+1):
        if -1<s-x-y<k+1:
            count += 1
print(count)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np
X,Y,A,B,C = list(map(int,input().split()))
p =list(map(int,input().split()))
p.append(0)
p.sort(reverse = True)
# print(p)
q=list(map(int,input().split()))
q.append(0)
q.sort(reverse = True)
r = list(map(int,input().split()))
r.append(0)
r.sort(reverse = True)

p = np.array(p)
q = np.array(q)
r = np.array(r)
kotae = 0
a,b,c = 0,0,0
for i in range(X+Y):
    if a >= X:
        p = p* 0
    if b >= Y:
        q = q*0
    if p[a] > q[b]:
        if p[a] > r[c]:
            kotae += p[a]
            a +=1
        else:
            kotae += r[c]
            c += 1
    else:
        if q[b] > r[c]:
            kotae += q[b]
            b +=1
        else:
            kotae += r[c]
            c += 1
    # print(kotae)
print(kotae)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import numpy as np
X,Y,A,B,C = list(map(int,input().split()))
p =list(map(int,input().split()))
p.append(0)
p.sort(reverse = True)
# print(p)
q=list(map(int,input().split()))
q.append(0)
q.sort(reverse = True)
r = list(map(int,input().split()))
r.append(0)
r.sort(reverse = True)
 
p = np.array(p)
q = np.array(q)
r = np.array(r)
kotae = 0
a,b,c = 0,0,0
d,e =False,False
for i in range(X+Y):
    if a >= X:
        if d == False:
            p = p* 0
            d = True
    if b >= Y:
        if e == False:
            q = q*0
            e = True
    if p[a] > q[b]:
        if p[a] > r[c]:
            kotae += p[a]
            a +=1
        else:
            kotae += r[c]
            c += 1
    else:
        if q[b] > r[c]:
            kotae += q[b]
            b +=1
        else:
            kotae += r[c]
            c += 1
    # print(kotae)
print(kotae)
### BUGGY CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

# def distribute(pos, full, tmp):
#     # read memo
#     if memo[pos][tmp] != None: return memo[pos][tmp]
#     # end
#     if tmp == 0: return 1
#     # next
#     ret = 0
#     if pos < N - 1:
#         for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
#     else: ret += 1
#     # print("###", pos, tmp, ret)
#     # write memo
#     if memo[pos][tmp] != None: memo[pos][tmp] = ret
#     return ret
def distribute(pos, full, tmp):
    return memo[pos][tmp]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

# create memo
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip
for i in range(N): memo[i][0] = 1
for j in range(1, ip_max + 1): memo[N - 1][j] = 1

M_tmp = M
ans = 1
ip_tmp = 0 # temporary size of memo
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## expand memo
    if i_p > ip_tmp: 
        for j in range(ip_tmp + 1, i_p + 1):
            memo_tmp = memo[N - 1][j - 1]
            for i in list(range(N - 1))[::-1]:
                memo_tmp += memo[i][j - 1]
                memo[i][j] = memo_tmp
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

### FIXED CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

ips = []
M_tmp = M
for p in range(2, int(math.sqrt(M)) + 1):
    if M_tmp % p > 0: continue
    for i_p in range(1, 33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    ips.append(i_p)
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break
else:
    ips.append(1)

#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    ptr_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        ptr_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips:
    ans = (ans * memo[i_p][0]) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)
### BUGGY CODE ###

#Mo
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]//700))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)