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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = [int(x) for x in readline().rstrip().split()]
B = [0] * 60
ans = 0
for i in range(N):
    i_bin = list(bin(A[i]))
    i_bin = i_bin[2:]
    i_bin = i_bin[::-1]
    k = 0
    for j in i_bin:
        if j == "1":
            B[k] += 1
        k += 1
B = np.array(B)

for q in range(60):
    temp = B[q] * (N - B[q])
    ans += (temp % (7 + 10 ** 9)) * ((2 ** q) % (7 + 10 ** 9))
    ans %= 7 + 10 ** 9
print(ans)    

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().rstrip().split()]
B = [0] * 60
ans = 0
for i in range(N):
    i_bin = list(bin(A[i]))
    i_bin = i_bin[2:]
    i_bin = i_bin[::-1]
    k = 0
    for j in i_bin:
        if j == "1":
            B[k] += 1
        k += 1

for q in range(60):
    temp = B[q] * (N - B[q])
    ans += (temp % (7 + 10 ** 9)) * ((2 ** q) % (7 + 10 ** 9))
    ans %= 7 + 10 ** 9
print(ans)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
point = [0]*n
for _ in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    p = p-1
    point[p] += x

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)    
 

### FIXED CODE ###

import sys 
sys.setrecursionlimit(10**6)
import sys
def input():
    return sys.stdin.readline()[:-1]
n, q = map(int, input().split())
G = [[] for _ in range(n)]
point = [0]*n
for _ in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    p = p-1
    point[p] += x

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
count = []
for i in range(n):
    j = i
    count.append(0)
    while j < n -1 and h[j] >= h[j+1]:
        count[i] += 1
        j += 1
print(max(count))


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
count = [0]*n
i = 0
while i < n:
    j = i
    while j < n -1 and h[j] >= h[j+1]:
        count[i] += 1
        j += 1
    i += count[i] + 1
print(max(count))
### BUGGY CODE ###

n = int(input())
ind = []
m = 0
k = 0
for i in range(n):
    a = int(input())
    if m == a:
        ind.append(i)
        k = a
    elif m < a:
        k, m = m, a
        ind = [i]
    elif k < a:
        k = a
print("\n".join(map(str, [k if i in ind else m for i in range(n)])))


### FIXED CODE ###

n = int(input())
ind = []
m = 0
k = 0
for i in range(n):
    a = int(input())
    if m == a:
        ind = -1
    elif m < a:
        k, m = m, a
        ind = i
    elif k < a:
        k = a
if ind == -1:
    print("\n".join(map(str, [m for i in range(n)])))
else:
    print("\n".join(map(str, [k if i == ind else m for i in range(n)])))
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    ans += 1
    _xor = A[i]
    _sum = A[i]
    for j in range(i + 1, n):
        _sum += A[j]
        _xor ^= A[j]
        if _sum == _xor:
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
A = [int(i) for i in input().split()]
_sum = 0
_xor = 0
l, r = 0, 0
ans = 0
while l < n:
    while r < n and _sum + A[r] == _xor ^ A[r]:
        _sum += A[r]
        _xor ^= A[r]
        r += 1
    ans += r - l
    _sum -= A[l]
    _xor ^= A[l]
    if l == r:
        r += 1
    l += 1

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

import numpy as np
n,k = map(int, input().split())
d = np.array(list(map(int, input().split())))
l = np.arange(n)
cnt = 0

def func(x_left, x_right):
  for i in range(n):
    temp_left = x_left[i]
    temp_right = x_right[i]
    if temp_left < 0:
      temp_left = 0
    if temp_right < 0:
      temp_right = n
    ans[temp_left:temp_right] += 1

while True:
  if cnt == k:
    break
  ans = np.array([0]*n)
  x_left = l-d
  x_right = l+d+1
  func(x_left, x_right)
  cnt += 1
  if np.all(d+n==ans):
    ans+=(k-cnt)*n
    break
  else:
    d = ans.copy()
    continue



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


### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

import numpy as np
import copy

N = int(input())

num_list = []

for i in range(N):
  num = int(input())
  num_list.append(num)
    
for i in range(N):
  dummy_list = copy.copy(num_list)
  del dummy_list[i]
  print(np.amax(dummy_list))

### FIXED CODE ###

N = int(input())

num_list = [int(input()) for i in range(N)]

sort_num_list = sorted(num_list)
max_n = sort_num_list[-1]
smax_n = sort_num_list[-2]

for i in num_list:
  if i==max_n:
    print(smax_n)
  else:
    print(max_n)
### BUGGY CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
for i in range(N):
  w,v=map(int,input().split())
  for j in range(100001):
    if j-v>=0:
      #print(dp[i-1][j-w[i]])
      dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=100000
#print(dp[0][:4])
while dp[-1][ans]>W:
  ans-=1
print(ans)

### FIXED CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
  
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()
### BUGGY CODE ###

n = int(input())
s = list(input())
cmin = n + 1
for i in range(n):
    c = s[:i].count("W") + s[i:].count("E")
    if cmin > c:
        cmin = c
print(cmin)


### FIXED CODE ###

n = int(input())
s = list(input())
c = s[1:].count("E")
ans = c
for i in range(1, n):
    c -= (1 if s[i] == "E" else 0)
    c += (1 if s[i - 1] == "W" else 0)
    ans = min(c, ans)
print(ans)
### BUGGY CODE ###

n=int(input())
a = [(1,1,1)]

def h(w):
    x,y,z = w
    x+=1
    y+=1
    z+=1
    return x**2+y**2+z**2+x*y+x*z+z*y

def g(x,y,z,w):
    return x**2+y**2+z**2+x*y+x*z+z*y == w

for w in range(1,n+1):
    a = list(filter(lambda b:h(b)>= w,a))
    b = []
    for x,y,z in a:
        if g(x,y,z,w):
            b.append((x,y,z))
        if g(x,y,z+1,w):
            b.append((x,y,z+1))
        if g(x,y+1,z,w):
            b.append((x,y+1,z))
        if g(x+1,y,z,w):
            b.append((x+1,y,z))
    b = list(set(b))
    a += b
    
    print(len(b))

### FIXED CODE ###

n=int(input())

arr = [[[0 for _ in range(101)] for _ in range(101)] for _ in range(101)]

def g(x,y,z):
    return x**2+y**2+z**2+x*y+x*z+y*z

table = [0]*10001

for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            re = g(i,j,k)
            if re <= 10000:
                table[re]+= 1



for i in range(1,n+1):
    print(table[i])
### BUGGY CODE ###

n = int(input())
l = []
for _ in range(n-1):
    l.append([int(i) for i in input().split()])
for j in range(n):
    l_ = l[j:]
    c = 0
    for i in range(n-1-j):
        if c <= l_[i][1]:
            c = l_[i][1]
        else:
            a = l_[i][1]
            while (c > a):
                a += l_[i][2]
            c = a
        c += l_[i][0]
    print(c)

### FIXED CODE ###

n = int(input())
l = []
for _ in range(n-1):
    l.append([int(i) for i in input().split()])
for j in range(n):
    l_ = l[j:]
    c = 0
    for i in range(n-1-j):
        if c <= l_[i][1]:
            c = l_[i][1]
        elif (c % l_[i][2] != 0):
            c = (c // l_[i][2] + 1) * l_[i][2]
        else:
            c = (c // l_[i][2]) * l_[i][2]
        c += l_[i][0]
    print(c)
### BUGGY CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    # f = factorial(N-1)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    f = factorial(N-1)
    def calc(k,slimes):
        if k == N-1:
            return 0
        r = 0


        for k in range(N-1):

            r += (slimes[-1]-slimes[-2-k]) * f // (N-k-1) % MOD

        return r % MOD
    
    print(int(calc(0,X)))




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    # f = factorial(N-1)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    f = factorial(N-1) % MOD
    def calc(k,slimes):
        r = 0

        for k in range(N-1):
            r += (slimes[-1]-slimes[-2-k]) * f * pow((N-k-1),MOD-2,MOD)
            r %= MOD
        return r
    print(calc(0,X))




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

N = int(input())
A = []

for i in range(N):
    a = int(input())
    A.append(a)

for i in range(N):
    ans = A[:i] + A[i+1:]
    print(max(ans))


### FIXED CODE ###

N = int(input())
A = []

for i in range(N):
    a = int(input())
    A.append(a)

x = sorted(A, reverse=True)

for i in range(N):
    if A[i] == x[0]:
        print(x[1])
    else:
        print(x[0])
### BUGGY CODE ###

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

def war(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

d=[[float("inf")]*N for _ in range(N)]
d2=[[float("inf")]*N for _ in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    if C>L:
        continue
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for i in range(N):
    d[i][i]=0

d=war(d)

for i in range(N):
    for j in range(N):
        if d[i][j]<=L:
            d2[i][j]=1
for i in range(N):
    d2[i][i]=0
d2=war(d2)
#print(d)
#print(d2)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    print(d2[s-1][t-1]-1 if d2[s-1][t-1]!=float("inf") else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M,L=map(int,input().split())

def war(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
INF=(L+1)*N
d=[[INF]*N for _ in range(N)]
d2=[[INF]*N for _ in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    if C>L:
        continue
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for i in range(N):
    d[i][i]=0

d=war(d)

for i in range(N):
    for j in range(N):
        if d[i][j]<=L:
            d2[i][j]=1
for i in range(N):
    d2[i][i]=0
d2=war(d2)
#print(d)
#print(d2)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    print(d2[s-1][t-1] %INF -1)
### BUGGY CODE ###

import numpy as np
N,M = map(int,input().split())
cards = list(map(int,input().split()))
exchange_lists=[]
for i in range (M):
  exchange_lists.append(list(map(int,input().split())))
exchange_lists.sort(key = lambda x:x[1],reverse=True)

def exchange_cards(cards,exchange):
  cards.sort()
  count = 0
  for i in range(len(cards)):
    if (exchange[1] > cards[i])and(exchange[0] > count):
      cards[i] = exchange[1]
      count += 1
    else:
      break
  return cards
      
for i in range(M):
  cards = exchange_cards(cards,exchange_lists[i])
print(np.sum(cards))

### FIXED CODE ###

import numpy as np
N,M = map(int,input().split())
cards = list(map(int,input().split()))
exchange_lists=[]
for i in range (M):
  exchange_lists.append(list(map(int,input().split())))
exchange_lists.sort(key = lambda x:x[1],reverse=True)
cards.sort()
count = 0
for i in range(M):
  exchange=exchange_lists[i]
  num = 0
  for j in range(count,N):
    if (exchange[1] > cards[j])and(exchange[0] > num):
      cards[j] = exchange[1]
      count += 1
      num+=1
    else:
      break
  
print(np.sum(cards))
### BUGGY CODE ###

n=int(input())
lista=[0 for i in range(n)]
lista=input().split()
n2=int(input())
listb=[0 for i in range(n2)]
listb=input().split()
cnt=0

for i in range(n2):
    x=0

    
    if int(lista[int(n/2)])>int(listb[i]):
        listc=[lista[k] for k in range(int(n/2))]
    
        for j in range(len(listc)):
            if listb[i]==listc[j] and x==0:
                
                x=1
                cnt+=1
    else: 
        listc=[lista[k] for k in range(int(n/2),n)]
      
        for j in range(len(listc)):
          
            if listb[i]==listc[j] and x==0:
               
                x=1
                cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
lista=[int(i) for i in input().split()]
n2=int(input())
listb=[int(i) for i in input().split()]
cnt=0


for i in listb:
    C=int(len(lista)/2)
    D=[0,len(lista)]
    while(1):
        if i<lista[C]:
            for k in D:
                if C>k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)

        elif i>lista[C]:
            for k in D:
                if C<k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)
        else:
            cnt+=1
            break
    
        if C==D[0]:
            break
    
        
print(cnt)
### BUGGY CODE ###

#

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

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

if n<3:
    print(abs(a[0]-a[-1]))
    exit()

c=[0]*n
c[-1]=0
mini=1000000

for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])


for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])

# print("?", c)

print(c[0])

### FIXED CODE ###

n, k=list(map(int, input().split()))
 
a=list(map(int, input().split()))
 
if n<3:
    print(abs(a[0]-a[-1]))
    exit()
 
c=[0]*n
c[-1]=0
mini=1000000
 
for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])
 
 
for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])
 
# print("?", c)
 
print(c[0])
### BUGGY CODE ###

import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


inf = float('inf')


def main():
  H, N = inputIntList()
  AB = [inputIntList() for _ in range(N)]
  dp = [inf for _ in range(H + 1)]

  dp[0] = 0
  for (a, m) in AB:
    for h in range(H):
      nxt = min(H, h+a)
      dp[nxt] = min(dp[h]+m, dp[nxt])
  # print(dp)
  return dp[H]


if __name__ == "__main__":
  print(main())


### FIXED CODE ###

import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


inf = float('inf')


def main():
  H, N = inputIntList()
  AB = [inputIntList() for _ in range(N)]
  dp = [inf for _ in range(H + 1)]

  dp[0] = 0
  for (a, m) in AB:
    for h in range(H):
      nxt = min(H, h+a)
      dp[nxt] = min(dp[h]+m, dp[nxt])
  # print(dp)
  return dp[H]


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

n,w = map(int, input().split())
values = [0]
weights = [0]
counter=0
for i in range(n):
    v,weight = map(int, input().split())
    values.append(v)
    weights.append(weight)

for i in range(1,n+1):
    counter=2
    while(w >= weights[i]*counter):
        weights.append(weights[i]*counter)
        values.append(values[i]*counter)
        counter = counter+1

dp = [[0 for i in range(w+1)]for j in range(len(values))]

for i in range(1,len(values)):
    for j in range(w+1):
        if(weights[i] > j):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])

print(dp[len(values)-1][-1])


### FIXED CODE ###

n,w = map(int, input().split())
values = []
weights = []

for i in range(n):
    v,weight = map(int, input().split())
    values.append(v)
    weights.append(weight)

dp = [0 for i in range(w+1)]

for i in range(n):
    for j in range(weights[i], w+1):
        dp[j] = max(dp[j], dp[j-weights[i]]+values[i])

print(dp[w])
### BUGGY CODE ###

def sigma(n,i,j):
    icnt=0
    stri=str(i)
    strj=str(j)
    for k in range(n):
        strk=str(k+1)
        if strk[0]==stri and strk[-1]==strj:
            icnt=icnt+1
    return icnt
            

n=int(input())
ncnt=0
for k in range(10):
    for m in range(10):
        s1=sigma(n,k,m)
        s2=sigma(n,m,k)
        ncnt=ncnt+s1*s2
print(ncnt)     

### FIXED CODE ###

def sigma2(n,i,j):
    if i==j and n<i:
        ncnt= 0
    elif i==j and i<=n:
        ncnt=1
    else:
        ncnt=0    

    if i*10+j<=n:
        ncnt=ncnt+1
        
    mcnt=-1
    nn=0
    for kt in range(1,6,1):
       for kt2 in range(10**kt):
           mcnt=mcnt+1
           nn=i*10**(kt+1)+kt2*10+j
           if nn>n:
               break
       if nn>n:
           break
               
    return mcnt+ncnt                


n=int(input())
ncnt=0
for k in range(1,10,1):
    for m in range(1,10,1):
        s1=sigma2(n,k,m)
        s2=sigma2(n,m,k)
        ncnt=ncnt+s1*s2
#        if s1*s2>0:
#            print(k,m,s1,s2)
print(ncnt)
### BUGGY CODE ###

def main():
    import sys

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, Q = MI()
    c = [{i} for i in LI()]

    unit = set()

    class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
        def __init__(self, N, unit):
            self.N = N
            self.unit = unit
            self.tree = [self.unit] * (2 * self.N)

        def build(self, init_value):  # 初期値を[N,2N)に格納
            for i in range(self.N):
                self.tree[i + self.N] = init_value[i]
            for i in range(self.N - 1, 0, -1):
                self.tree[i] = self.tree[i << 1] | self.tree[i << 1 | 1]

        def fold(self, L, R):  # [L,R)の区間取得
            L += self.N
            R += self.N
            vL = self.unit
            vR = self.unit
            while L < R:
                if L & 1:
                    vL = vL | self.tree[L]
                    L += 1
                if R & 1:
                    R -= 1
                    vR = self.tree[R] | vR
                L >>= 1
                R >>= 1
            return len(vL | vR)

    seg = SegTree(N, unit)
    seg.build(c)

    for i in range(Q):
        l, r = MI()
        print(seg.fold(l - 1, r))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((i,l,r))

    from operator import itemgetter

    lr = sorted(lr,key=itemgetter(2))  # 右端rでソート
    a = 0
    d = {}  # d[i] = 玉iが現れた最も右の位置
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  # i(1-index)番目の値を+x
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

        def query(self, i):  # 1番目からi(1-index)番目までの和を返す
            res = 0
            while i > 0:
                res += self.tree[i]
                i -= i & (-i)
            return res


    bit = BIT([0]*N)  # 最も右に現れた玉の位置を管理
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][2] == i:
            j,l,r = lr[a]
            ANS[j] = bit.query(r)-bit.query(l-1)
            a += 1

    print(*ANS,sep='\n')


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

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

for i in range(1,n):
  if(a[i-1] > a[i]):
    while(a[i-1] != a[i]):
      a[i] += 1
      ans += 1
    
print(ans)

### FIXED CODE ###

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

for i in range(1,n):
  if(a[i-1] > a[i]):
    diff = a[i-1] - a[i]
    a[i] += diff
    ans += diff
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, (n + 1)):
  print(a.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
anslist = [0] * n
for i in a:
  anslist[i - 1] += 1
for i in anslist:
  print(i)