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

def main():
    import bisect
    import math
    import sys

    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    for i in range(m):
        tmp=a[n-1]//2
        bisect.insort_left(a,tmp)
        a.pop(n)
    print(sum(a))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    import math
    import sys
    import heapq
    def f(s):
        return -int(s)

    n,m=map(int,input().split())
    a=list(map(f,input().split()))
    heapq.heapify(a)

    for i in range(m):
        tmp=heapq.heappop(a)
        tmp=math.ceil(tmp/2)
        heapq.heappush(a,tmp)

    print(-sum(a))
    

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

import sys
#input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    S = input()
    
    l = []
    base = 1
    for st in S[::-1]:
        l.append((int(st)*base)%2019)
        base *= 10
        
    cum = 0
    d = defaultdict(int)
    d[0] = 1
    
    ans = 0
    for num in l:
        cum += num
        ans += d[cum%2019]
        d[cum%2019] += 1

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


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

    c = Counter(MOD_list)
    for v in c.values():
        ans += (v*(v-1))//2
        
    print(ans)

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

N=int(input())
h_list=[int(x) for x in input().split()]
flag=True
for i in range(len(h_list)-1):    
    tmp=h_list[i:]
    for i in range(len(tmp)-1):        
        if tmp[0]-tmp[i+1]>=2:
            flag=False
            break
        
if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

flag=True

m=h_list[0]
for j in range(len(h_list)-1):
    if m<h_list[j]:
        m=h_list[j]
    if m-h_list[j+1]>=2:
        flag=False
        break        
    
if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

def main():
    S = readline().strip().decode('utf-8')
    Q = int(readline())
    Query = [tuple(readline().decode('utf-8').split()) for _ in range(Q)]
    rev_flg = 0
    for q in Query:
        if q[0] == '1':
            rev_flg += 1
        else:
            if int(q[1])-(rev_flg%2) == 1:
                S = q[2] + S
            else:
                S += q[2]
    if rev_flg%2 == 1:
        S = S[::-1]
    print(S)

    return
if __name__ == '__main__':
    main()



### FIXED CODE ###

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

def main():
    from collections import deque
    S = deque(readline().strip().decode())
    Q = int(readline())
    Query = readlines()
    rev_flg = False
    for q in Query:
        if q[0] == ord('1'):
            rev_flg = not rev_flg
        else:
            _, f, c = q.decode().split()
            if int(f)-(rev_flg) == 1:
                S.appendleft(c)
            else:
                S.append(c)
    S = ''.join(S)
    if rev_flg is True:
        S = S[::-1]
    print(S)

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

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
  if S[i] == 'R':
    R.append(i)
  elif S[i] == 'G':
    G.append(i)
  else:
    B.append(i)
    
count = 0

for r in R:
  for g in G:
    len_B = len(B)
    if (r+g)%2==0 and (r+g)//2 in B:
      len_B -= 1
    if 2*r-g in B:
      len_B -= 1
    if 2*g-r in B:
      len_B -= 1
    count += len_B
      
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = 0
G = 0
B = 0

for i in range(N):
  if S[i] == 'R':
    R += 1
  elif S[i] == 'G':
    G += 1
  else:
    B += 1
    
count = 0
for i in range(N-1):
  for j in range(i+1,N):
    if 2*j-i>=N:
      break
    if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
      count += 1

print(R*G*B-count)
### BUGGY CODE ###

s=input()

cnts=[0]*2019

cnts[0]=1

for i in range(len(s)):
  tmp=int(s[i:])%2019
  cnts[tmp]+=1

ans=0
for cnt in cnts:
  ans+=cnt*(cnt-1)//2
  
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
# s=input()
#https://atcoder.jp/contests/abc158/tasks/abc158_e p=2019 copype
P=2019

# N,P=map(int,input().split());
S,a,i,j,c=input(),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i,j=(i+int(v)*j)%P,j*10%P;a+=c[i];c[i]+=1
else:
	for v in S:
		i+=1
		if int(v)%P<1:a+=i
print(a)

#honto???
### BUGGY CODE ###

n = int(input())
m = n

exp = []
div = []
for i in range(2, int(n**(1/2))+2):
    cnt = 0
    if n%i == 0:
        div.append(n//i)
        while n%i == 0:
            cnt += 1
            n //= i
        exp.append(cnt)

for i in div:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    if cnt >= 1:
        exp.append(cnt)

if n == m and m > 1:
    exp.append(1)

opr = 0
for x in exp:
    for i in range(x+1):
        if i*(i+1)//2 <= x < (i+1)*(i+2)//2:
            opr += i
            break

print(opr)

### FIXED CODE ###

n = int(input())
m = n

exp = []

cnt = 0
while n%2 == 0:
    cnt += 1
    n //= 2
if cnt > 0:
    exp.append(cnt)

i = 3
while i*i <= n:
    cnt = 0
    while n%i == 0:
        cnt += 1
        n //= i
    exp.append(cnt)
    i += 2

if n != 1:
    exp.append(1)

opr = 0
for x in exp:
    opr += int((-1+(8*x+1)**(1/2))/2)

print(opr)
### BUGGY CODE ###

import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = float('inf') 
(H, W) = list(map(int,input().split()))
# print(H,W)

S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

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

for i in range(H):
    S.append(input())

#print(S)

def vindex(i,j):
    global W
    return W * (i-1) + j -1

# print(vindex(H,W))
for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        # print(index,s)
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1

#print("D",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])
    #print(k,d)

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in a:
    b.append(i)
    b.reverse()
print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
o = [a[i] for i in range(2,n,2)]
e = [a[h] for h in range(1,n,2)]
if n%2 == 0:
    e.reverse()
    l = e + [a[0]] + o
    print(*l)
else:
    o.reverse()
    l = o + [a[0]] + e
    print(*l)
### BUGGY CODE ###

N = int(input())
A = list(input().split())
B = [0 for i in range(N)]
for i in range (N-1):
  for j in range (1,N+1):
    if int(A[i])==j:
      B[j-1]=B[j-1]+1
[print(i) for i in B]
 
    

### FIXED CODE ###

import collections
N = int(input())
A = list(input().split())
c=collections.Counter(A)
for i in range (1,N+1):
    print(c[str(i)])
### BUGGY CODE ###

import itertools
import collections
import math
N,A=map(int,raw_input().split())
#print N,A
x=collections.Counter(map(int,raw_input().split()))
#print x

iv=[i for i in x.keys()]	#Item value
ic=[]	#Item count
for i in x.items():
	tmp=[i for i in range(i[1]+1)]
	ic.append(tmp)


ic_n=[len(_)-1 for _ in ic]

p=list(itertools.product(*ic))
#print "# p"
#print p		#Pattern

a=[]
for m in p:
	t_sum=0
	for j,k in zip(m,iv):
		t_sum+=j*k
	#print t_sum,len(m)
	if sum(m)!=0 and t_sum/sum(m)==A and t_sum%sum(m)==0 and sum(m)!=0:
		#print m,iv,t_sum,sum(m)
		a.append(m)

#print "# a"
#print a

def combination(n,r):
	g=[math.factorial(i) for i in range(100) ]
	return int(g[n]/(g[r]*g[n-r]))

ans=0
for i in a:
	t_cnt=1
	for j,k in zip(i,ic_n):
		if j!=0 or j!=k:
			t_cnt*= combination(k,j)
			pass
	#print t_cnt
	ans+=t_cnt
print ans


### FIXED CODE ###

N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x
y=map(lambda i:i-A, x)
#print y

max_x=max(max(x),A)
#print max_x

dp=[[0]*(2*N*max_x+1) for i in range(N+1)]

for j in range(N+1):
	for t in range(2*N*max_x):
		if j==0 and t==N*max_x:
			dp[j][t]=1
		elif j>=1 and (t-y[j]<0 or t-y[j]>2*N*max_x):
			dp[j][t]=dp[j-1][t]
		elif j>=1 and t-y[j]>=0 and 2*N*max_x>=t-y[j]: 
			dp[j][t]=dp[j-1][t]+dp[j-1][t-y[j]]
		else:
			dp[j][t]=0

print dp[N][N*max_x]-1
### BUGGY CODE ###

# -*- coding:utf-8 -*-
def my_pow(x,n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow((x**2),int(n/2))
    else:
        return pow(x,int(n-1))*x
    
n,m = map(int,input().split())
x = 1000000007
print(my_pow(n,m)%x)

### FIXED CODE ###

def mpow(x,n,mod):
    if n == 0:
        return 1
    if n % 4 == 0:
        return mpow((x**4)%mod,int(n/4),mod)
    elif n%4 == 1:
        return (mpow(x,int(n-1),mod)*x)%mod
    elif n%4 == 2:
        return (mpow(x,int(n-2),mod)*(x**2))%mod
    elif n%4 == 3:
        return (mpow(x,int(n-3),mod)*(x**3))%mod
n,m = map(int,input().split())
mod = 1000000007
print(mpow(n,m,mod))
### BUGGY CODE ###

#!/usr/bin/env python
#-*- coding:utf-8 -*-
while True:
	n = input()
	if n == 0: break
	a = [ input() for i in xrange(n) ]
	m = -100000
	for i in xrange(n):
		for j in xrange(n + 1):
			m = max(m, sum(a[i:j]))
	print m

### FIXED CODE ###

#!/usr/bin/env python
#-*- coding:utf-8 -*-
while True:
	n = input()
	if n == 0: break
	a = [ input() for i in xrange(n) ]
	m = -100000
	for i in xrange(n):
		s = 0
		for j in xrange(i, n):
			s += a[j]
			m = max(m, s)
	print m
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    if s == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(s)*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
"""
#print(dp)
print(dp[N-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

n,m=map(int,input().split())
if abs(n-m)>1:
    print(0)
elif n==m:
    prod=1
    for i in range(1,n+1):
        prod*=i
    print(prod*prod*2%1000000007)
else:
    prod=1
    for i in range(1,min(m,n)+1):
        prod*=i
    print(prod*prod*max(m,n)%1000000007)


### FIXED CODE ###

n,m=map(int,input().split())
if abs(n-m)>1:
    print(0)
elif n==m:
    prod=1
    for i in range(1,n+1):
        prod*=i
        prod%=1000000007
    print(prod*prod*2%1000000007)
else:
    prod=1
    for i in range(1,min(m,n)+1):
        prod*=i
        prod%=1000000007
    print(prod*prod*max(m,n)%1000000007)
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    R, C, k = map(int, input().split())
    s = [[0] * (C + 1) for i in range(R + 1)]
    dp = [[[0] * 4 for i in range(C + 1)] for j in range(R + 1)]
    for i in range(k):
        r, c, v = map(int, input().split())
        s[r][c] = v
    for i in range(R):
        for j in range(C):
            m = max(dp[i][j + 1][0], dp[i][j + 1][1], dp[i][j + 1][2], dp[i][j + 1][3])
            for k in range(4):
                if k == 0:
                    dp[i + 1][j + 1][k] = max(dp[i + 1][j][k], m)
                else:
                    dp[i + 1][j + 1][k] = max(dp[i + 1][j][k], dp[i + 1][j][k - 1] + s[i + 1][j + 1])
            dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1], s[i + 1][j + 1] + m)
    print(max(dp[R][C]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    R, C, k = map(int, input().split())
    s = [[0] * (C + 1) for i in range(R + 1)]
    dp = [[[0] * (C + 1) for i in range(R + 1)] for j in range(4)]
    for i in range(k):
        r, c, v = map(int, input().split())
        s[r][c] = v
    for i in range(R):
        for j in range(C):
            m = max(dp[0][i][j + 1], dp[1][i][j + 1], dp[2][i][j + 1], dp[3][i][j + 1])
            for k in range(4):
                if k == 0:
                    dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], m)
                else:
                    dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], dp[k - 1][i + 1][j] + s[i + 1][j + 1])
            dp[1][i + 1][j + 1] = max(dp[1][i + 1][j + 1], s[i + 1][j + 1] + m)
    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break

    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
    xg -= 1
    yg -= 1

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[-1] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            c = S[i]
            prevc = S[i-k]
            if i-k >= 0 and prevc == "D":
                d_cnt -= 1
                dm_cnt -= m_cnt
            elif i-k >= 0 and prevc == "M":
                m_cnt -= 1
            if c == "D":
                d_cnt += 1
            elif c == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif c == "C":
                answer += dm_cnt
        print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            c = S[i]
            if i-k >= 0:
                prevc = S[i-k]
                if prevc == "D":
                    d_cnt -= 1
                    dm_cnt -= m_cnt
                elif prevc == "M":
                    m_cnt -= 1
            if c == "D":
                d_cnt += 1
            elif c == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif c == "C":
                answer += dm_cnt
        print(answer)


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

from collections import defaultdict
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))


que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])