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

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
A = Counter(a)

for i in range(n):
    N = a[i]
    ans = 0
    for x,y in A.items():
        if x == N:
            y -= 1
        ans += y*(y-1)//2
    print(ans)

### FIXED CODE ###

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

a = list(set(A))
a_c = {}
for v in A:
  if v in a_c:
    a_c[v] += 1
  else:
    a_c[v] = 1

def cmb(n):
  if n < 2: return 0
  else:
    return n * (n-1)//2

S = 0
for k in a_c:
  S += cmb(a_c[k])

for i in range(N):
  print(S - cmb(a_c[A[i]]) + cmb(a_c[A[i]]-1))
### BUGGY CODE ###

import numpy as np
s=input()

ss=[]
for i in range(len(s)):
    ss.append(s[i])
arr=np.array(ss)

q=int(input())
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        arr=arr[::-1]
        
    else:
        if l[1]=="1":
            arr=arr[::-1]
            arr=np.hstack((arr,l[2]))
            arr=arr[::-1]
        if l[1]=="2":
            arr=np.hstack((arr,[l[2]]))
        

a=arr.tolist()
for i in a:
    print(i,end="")

### FIXED CODE ###


s=input()
q=int(input())
p=0
a=""
b=""
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        p=(p+1)%2
    else:
        if p==0:
            if l[1]=="1":
                a+=l[2]
            else:
                b+=l[2]
        else:
            if l[1]=="1":
                b+=l[2]
            else:
                a+=l[2]
if p==1:
    print(b[::-1]+s[::-1]+a)
else:
    print(a[::-1]+s+b)
### BUGGY CODE ###

import copy
import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
for i in range(n):
    l_o = copy.copy(l_a)
    del l_o[i]
    c = collections.Counter(l_o)
    #print(c)
    #print(c.values())
    Ans = 0
    for i in range(len(list(c.values()))):
        for j in range(list(c.values())[i] - 1):
            Ans += (j + 1)

    print(Ans)

### FIXED CODE ###

import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
d_c = collections.Counter(l_a)
l_c = list(d_c.values())

#N個から選ぶ方法
o = 0
for i in range(len(l_c)):
    if(l_c[i] != 1):
        o += int((l_c[i] - 1) * l_c[i] / 2)

#Output
for i in range(n):
    print(o - d_c[l_a[i]] + 1)
### BUGGY CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
tb = 1
for i in range(K):
  tb *= A[i]
for i in range(K,N):
  t = tb // A[i-K]
  t *= A[i]
  if t > tb:
    print("Yes")
  else:
    print("No")
  tb = t


### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(K,N):
  if A[i-K] < A[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        b=l.index(now)
        c=count-b
        a=1
    else:
        l.append(now)
if count==K:
    print(now)
else:
    n=int((K-2)/c)
    ncount=0
    while ncount <n:
        now=A[now-1]
        count+=1
    print(now)
    


### FIXED CODE ###

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

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():

    from collections import deque

    H, W = map(int, input().split())
    maze = [input() for i in range(H)]
    start_list=[]
    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                start_list.append([i,j])
    INF = 10 ** 20

    visited = [[INF] * W for j in range(H)]


    def bfs(maze):
        queue = deque()
        for [i,j] in start_list:
            queue.append([i,j])
            visited[i][j]=0
        while queue:
            y, x = queue.popleft()
            cnt=0
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and \
                        maze[ny][nx] == "." and visited[ny][nx]==INF:
                        visited[ny][nx] = visited[y][x] + 1
                        queue.append([ny, nx])
        return visited

    bfs(maze)
    print(np.amax(visited))


resolve()

### FIXED CODE ###

def resolve():

    from collections import deque

    H, W = map(int, input().split())
    maze = [input() for i in range(H)]
    start_list=[]
    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                start_list.append([i,j])
    INF = 10 ** 20

    visited = [[INF] * W for j in range(H)]


    def bfs(maze):
        queue = deque()
        for [i,j] in start_list:
            queue.append([i,j])
            visited[i][j]=0
        while queue:
            y, x = queue.popleft()
            cnt=0
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and \
                        maze[ny][nx] == "." and visited[ny][nx]==INF:
                        visited[ny][nx] = visited[y][x] + 1
                        queue.append([ny, nx])
        return visited


    bfs(maze)
    ans=0
    for i in range(H):
        for j in range(W):
            ans=max(ans,visited[i][j])

    print(ans)


resolve()
### BUGGY CODE ###

n, k, *A = map(int, open(0).read().split())

#n, k = map(int, input().split())
#A = [int(a) for a in input().split()]
Jump = [None] * n
Jump[0] = 1
next = 0
for i in range(1,n+1):
    to = A[next]
    if to in Jump:
        start = Jump.index(to)
        end = i
        dis = end - start

        roop = (k-start) % dis
        print(Jump[start+roop])
        break

    Jump[i] = to
    next = to-1
    if i ==k:
        print(to)
        break


### FIXED CODE ###

n, k = map(int, input().split())
A = [int(a) for a in input().split()]
Jump = [None] * n
Jump[0] = 1
Rireki = [-1] * (n+1)
Rireki[0] = 0
next = 0
for i in range(1,n+1):
    to = A[next]

    if Rireki[to] >= 0:
        start = Jump.index(to)
        end = i
        dis = end - start

        roop = (k-start) % dis
        print(Jump[start+roop])
        break
    Rireki[to] = i
    Jump[i] = to
    next = to-1
    if i ==k:
        print(to)
        break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
PX=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
  a-=1
  b-=1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for p,x in PX:
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:
      continue
    dfs(i,g)
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q=map(int,input().split())
c=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  c[a].append(b)
  c[b].append(a)
px=[0]*n
for I in range(q):
    p,x=map(int,input().split())
    px[p-1]+=x 
ans=[0]*n
def dfs(g,h=-1):
  ans[g]=ans[h]+px[g]
  for i in c[g]:
    if i==h:continue
    dfs(i,g)
dfs(0)
print(*ans)
### BUGGY CODE ###

from math import factorial
from collections import defaultdict


ball_num = int(input().rstrip())
points = [int(n) for n in input().rstrip().split()]

for ban_i in range(ball_num):
    point_dict=defaultdict(int)
    pattern_num=0
    for i in range(ball_num):
        if i==ban_i:
            continue

        point_dict[points[i]]+=1
        
    for j in point_dict:
        if point_dict[j]>=2:
            
            pattern_num += factorial(point_dict[j])//(2*factorial(point_dict[j]-2))
            
        
    print(pattern_num)

### FIXED CODE ###

from collections import defaultdict


ball_num = int(input().rstrip())
points = [int(n) for n in input().rstrip().split()]
point_dict=defaultdict(int)
total_pattern=0

for i in range(ball_num):
    point_dict[points[i]]+=1
for j in point_dict:
    total_pattern += point_dict[j]*(point_dict[j]-1)//2
    
total_pattern0=total_pattern
for ban_i in range(ball_num):
    total_pattern0 -= point_dict[points[ban_i]]*(point_dict[points[ban_i]]-1)//2         
    total_pattern0 += (point_dict[points[ban_i]]-1)*(point_dict[points[ban_i]]-2)//2
        
    print(total_pattern0)
    total_pattern0=total_pattern
### BUGGY CODE ###

c = []
for i in range(3):
    c.append(list(map(int, input().split())))

for a1 in range(max(c[0][0], c[0][1], c[0][2]) + 1):
    for a2 in range(max(c[1][0], c[1][1], c[1][2]) + 1):
        for a3 in range(max(c[2][0], c[2][1], c[2][2]) + 1):
            for b1 in range(max(c[0][0], c[1][0], c[2][0]) + 1):
                for b2 in range(max(c[0][1], c[1][1], c[2][1]) + 1):
                    for b3 in range(max(c[0][2], c[1][2], c[2][2]) + 1):
                        if a1 + b1 == c[0][0] and \
                           a1 + b2 == c[0][1] and \
                           a1 + b3 == c[0][2] and \
                           a2 + b1 == c[1][0] and \
                           a2 + b2 == c[1][1] and \
                           a2 + b3 == c[1][2] and \
                           a3 + b1 == c[2][0] and \
                           a3 + b2 == c[2][1] and \
                           a3 + b3 == c[2][2]:
                            print('Yes')
                            exit()
print('No')


### FIXED CODE ###

c = []
for i in range(3):
    c.append(list(map(int, input().split())))

x = [0] * 3
y = [0] * 3

for i in range(3):
    y[i] = c[0][i] - x[0]
for i in range(3):
    x[i] = c[i][0] - y[0]

for i in range(3):
    for j in range(3):
        if x[i] + y[j] != c[i][j]:
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

from collections import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return Counter(divisors)
 
n,*a=map(int,open(0).read().split())
ans=Counter()
for i in range(n):
    ans+=dv(a[i])
l=[]
for k,v in ans.items():
    if v==n-1 or v==n:
        l.append(k)
print(max(l))

### FIXED CODE ###

from collections import*
from functools import*
from fractions import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return Counter(divisors)

n,*a=map(int,open(0).read().split())
if n<1000:
    ans=Counter()
    for i in range(n):
        ans+=dv(a[i])
    l=[]
    for k,v in ans.items():
        if v==n-1 or v==n:
            l.append(k)
    print(max(l))
else:
    print(max(reduce(gcd,a[n//4:]),reduce(gcd,a[:n//4]+a[n//2:]),reduce(gcd,a[:n//2]+a[3*n//4:]),reduce(gcd,a[:3*n//4])))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split(' ')]

order = []

for attendance in range(1, N + 1):
    for student in range(len(A)):
        studentNumber = student + 1
        numberOfStudents = A[student]

        if numberOfStudents == attendance:
            order.append(str(studentNumber))

print(" ".join(order))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split(' ')]

order = sorted(range(len(A)), key=lambda k: A[k])
order = [str(x + 1) for x in order]

print(" ".join(order))
### BUGGY CODE ###

import sys

def solve(N, A):
    def moutain(x):
        sum = 0
        for i in range(N):
            sum += A[(x+i)%N] * (-1) ** (i)
        return sum

    m = [int()] * N
    for i in range(N):
        m[i] = str(moutain(i))

    print(' '.join(m))

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

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def solve(N, A):
    m = [int()] * (N)
    for i in range(N):
        m[0] += A[i] * (-1)**i

    for i in range(1, N):
        m[i] = ((A[i-1]) * 2 - m[i-1])

    m = map(str, m)
    print(' '.join(m))

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

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

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])
"""
for bc in BC:
    bc = [int(i) for i in bc]
"""
#print(BC)

for bc in BC:
    for i in range(0,len(A)):
        if A[i] == bc[0]:
            A[i] = bc[1]
  #  print("A:",A)
    print (sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])

#print(BC)
yoso_count=[]
for i in range(1,10**5+1):
    yoso_count.append([i,0])

sum = 0
for a in A:
    yoso_count[int(a)-1][1] += 1
    sum += a

#print(yoso_count,sum)

for bc in BC:
    sum += (bc[1] - bc[0])*yoso_count[bc[0]-1][1]
    yoso_count[bc[1]-1][1] += yoso_count[bc[0]-1][1]
    yoso_count[bc[0]-1][1] = 0
    print(sum)
### BUGGY CODE ###

#ALDS1_4-B BinarySearch
import heapq

S = []
T = []
n=input()
S = input().split()
q=input()
T = input().split()
c=0
heapq.heapify(S)
heapq.heapify(T)
for t in T:
    if(t in S):c+=1
        
print(c)

### FIXED CODE ###

#ALDS1_4-B BinarySearch
input()
S=input().split()
input()
T=input().split()
print(len(set(S)&set(T)))
### BUGGY CODE ###

n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        if c==dps[int(ii)-1]:
            continue
        idx=bisect.bisect_left(d[c],int(ii)-1)
        d[c].insert(idx,int(ii)-1)
        d[c].sort()
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass

### FIXED CODE ###

n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        if c==dps[int(ii)-1]:
            continue
        bisect.insort_left(d[c],int(ii)-1)
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[8]:


N,Q = map(int, input().split())
S = input()
mylist = []
for i in range(len(S)-1):
    if S[i] == "A" and S[i+1] == "C":
        mylist.append(i)
for _ in range(Q):
    l,r = map(int, input().split())
    ans = [1 for x in mylist if l-1<= x and x+1<=r-1]
    print(sum(ans))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[15]:


N,Q = map(int, input().split())
S = list(input())
mylist = [0]
cnt = 0
for i in range(1,len(S)):
    if S[i-1] == "A" and S[i] == "C":
        cnt += 1
    mylist.append(cnt)
for _ in range(Q):
    l,r = map(int, input().split())
    ans = mylist[r-1] - mylist[l-1]
    print(ans)


# In[ ]:
### BUGGY CODE ###

X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 0
    a = x
    b = x
    while ans == 0:
      if a < 0:
        a = 0
      if b > N-1:
        b = N-1
      if X-i != P[a]:
        ans = X-i
      elif X+i != P[b]:
        ans = X+i
        a -= 1
      else:
        a -= 1
        b += 1
        i += 1
print(ans)

### FIXED CODE ###

X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 1
    a = x-1
    b = x+1
    m = min(P[N-1]-X, X-P[0])
    for i in range(1,m+2):
      if a < 0:
        a = 0
      if b > N-1:
        b = N-1
      if X-i != P[a]:
        ans = X-i
        break
      elif X+i != P[b]:
        ans = X+i
        break
      else:
        a -= 1
        b += 1
print(ans)
### BUGGY CODE ###

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

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

d.sort()
t.sort()

flag = True
for i in range(len(t)):
    if t[i] in d:
        del d[d.index(t[i])]
    else:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

d.sort()
t.sort()

d = array_count(d)
t = array_count(t)

for i in range(len(t)):
    t[i][1] = -1 * t[i][1]
    d.append(t[i])

d.sort()

for i in range(1,len(d)):
    if d[i-1][0] == d[i][0]:
        d[i-1][1] = d[i-1][1] + d[i][1]
        d[i][1] = 0

flag = True

for i in range(len(d)):
    if d[i][1] < 0:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])
ans = 0
for i in range(N):
    ans += lcm // A[i]
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

def prime_factorize(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

primes = defaultdict(int)
for a in A:
    for x, p in prime_factorize(a):
        primes[x] = max(primes[x], p)
lcm = 1
for prime, ind in primes.items():
    lcm *= prime ** ind
ans = 0
for i in range(N):
    ans += lcm // A[i]
    if i == N // 2:
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

from itertools import product
def gcd(a, b, c):
    z = min(a, b, c)
    for i in range(z, 0, -1):
        if a%i==0 and b%i==0 and c%i==0:
            return i

k = int(input())

d = {}

totsum = 0
for i in range(1, k+1):
    for j in range(i, k+1):
        for k in range(j, k+1):
            if i ==j ==k:
                totsum += i
                continue

            elif i==j or i==k or j==k: factor = 3
            else: factor = 6

            if i ==1 or j==1 or k==1: 
                totsum += 1*factor
                continue

            totsum += gcd(i, j, k)*factor

print(totsum)




### FIXED CODE ###

k = int(input())
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

def gcd_list(l):
    if len(l) == 0:
        l.append(0)
    res = l[0]
    for i in range(len(l)):
        res = gcd(res, l[i])
    return res

m = []
left = 0
for i in range(n):
    if i == 0:
        left = 0
    else:
        left = gcd(left, A[i-1])
        
    right = gcd_list(A[i+1:])
    m.append(gcd(left, right))

print(max(m))

### FIXED CODE ###

from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

m = []
left = [0]
right = [0]
for i in range(n):
    left.append(gcd(left[i], A[i]))
    right.append(gcd(right[i], A[n-i-1]))
    

for i in range(n):
    m.append(gcd(left[i], right[n-i-1]))
    
print(max(m))
### BUGGY CODE ###

n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

### FIXED CODE ###


def hoge():

    n, p = [int(c) for c in input().split()]
    s = input()    

    if p in (2,5):
        a = tuple(int(c)%p for c in s)
        out = 0
        for i,x in enumerate(a):
            if x==0:
                out += (i + 1)
    else:
        a = [0]*n
        tmp = 0
        for i in reversed(range(n)):
            tmp = (tmp + pow(10, n-i-1, p) * int(s[i])) % p
    #         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
            a[i] = tmp
        d = {i: 0 for i in range(p)}
        d[0] = 1
        out = 0
        for x in a[::-1]:
            out += d[x]
            d[x] += 1
    print(out)
hoge()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

def seg_function(x,y): # Segment treeで扱うfunction
    return x|y

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[set()]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]={C[i]}

for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el): # A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=set()

    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for i in range(Q):
    x,y=map(int,input().split())
    print(len(getvalues(x-1,y)))


### FIXED CODE ###

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")