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

import numpy as np

n = int(input())
a_array = np.array([int(elem) for elem in input().split(' ')])


def calculate_cumulative_sum(a_array, n):
    cumul_sum_array = np.zeros(n, dtype=np.int32)
    cumul_sum_array[0] = a_array[0]
    for i in range(1, n):
        cumul_sum_array[i] = cumul_sum_array[i - 1] + a_array[i]
    return cumul_sum_array


def check_1(cumul_sum_array):
    result = (cumul_sum_array != 0).all()
    return result


def check_2(cumul_sum_array):
    odd = np.sign(cumul_sum[::2])
    even = np.sign(cumul_sum[1::2])
    odd_sign = np.unique(odd)
    even_sign = np.unique(even)
    return (len(odd_sign) == 1) * (len(even_sign) == 1) * (odd_sign[0] != even_sign[0])


cumul_sum = calculate_cumulative_sum(a_array, n)
count = {'plus': 0, 'minus': 0}

def calc_num_manipulation(cumul_sum, start, n):
    cumul_sum = cumul_sum.copy()
    count = 0
    for i in range(n):
        if check_1(cumul_sum) and check_2(cumul_sum):
            break
        else:
            if i == 0:
                diff = cumul_sum[i] - start
                count += abs(diff)
                cumul_sum[i:] -= diff
            else:
                if cumul_sum[i - 1] < 0 and cumul_sum[i] <= 0:
                    diff = cumul_sum[i] - 1
                    count += abs(diff)
                    cumul_sum[i:] -= diff
                elif cumul_sum[i - 1] > 0 and cumul_sum[i] >= 0:
                    diff = cumul_sum[i] - (-1)
                    count += abs(diff)
                    cumul_sum[i:] -= diff
                else:
                    continue
    return count

count['plus'] = calc_num_manipulation(cumul_sum, 1, n)
count['minus'] = calc_num_manipulation(cumul_sum, -1, n)
print(min(count.values()))


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split(' ')))

def count_manipulation(a_list, start):
    assert start in (0, 1)
    sum = 0
    count = 0
    for i, a in enumerate(a_list):
        sum += a
        if i % 2 == start:
            if sum > 0:
                continue
            else:
                diff = 1 - sum
                count += diff
                sum += diff
        else:
            if sum < 0:
                continue
            else:
                diff = sum - (-1)
                count += diff
                sum -= diff
    return count

count_plus = count_manipulation(a_list, 0)
count_minus = count_manipulation(a_list, 1)
print(min(count_plus, count_minus))
### BUGGY CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
new1 = [[] for i in range(N)]
new2 = [[] for i in range(N)]
new3 = [[] for i in range(N)]
for i in range(N):
    for v in graph[i]:
        new1[i].append(v)
for i in range(N):
    for v in graph[i]:
        new2[i].extend(new1[v])
for i in range(N):
    for v in graph[i]:
        new3[i].extend(new2[v])
#print(new1)
#print(new2)
#print(new3)



visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v, T):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        #print(con)
        con = list(set(new3[v]))
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
            if u == T:
                return()
bfs(S,T)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v+N)
    graph[u+N].append(v+2*N)
    graph[u+2*N].append(v)
S, T = map(int,input().split())
S, T = S-1, T-1
visit = [False for i in range(3 * N)]
length = [0 for i in range(3 * N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while Q:
        v = Q.pop(0)
        for u in graph[v]:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(int(length[T] //3))
else:
    print(-1)
### BUGGY CODE ###

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

ans = []
for i in range(n):
    ans.append(A.index(i+1)+1)

print(' '.join(str(a) for a in ans))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
 
 
k = sorted(range(0,n),key=lambda x:l[x])
for i in k:
    print(i+1,end= " ")
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

MOD = 10**9+7
N = int(readline())
C = list(map(int, readline().split()))
C.sort()

ans = 0
for i in range(N):
    ans = (ans + pow(2, 2*N-2)*C[i]*(N-i+1))%MOD
print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline

MOD = 10**9+7
N = int(readline())
C = list(map(int, readline().split()))
C.sort()

ans = 0
for i in range(N):
    ans = (ans + pow(2, 2*N-2, MOD)*C[i]*(N-i+1))%MOD
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = len(set(A))
count = []

if L <= K:
  print(0)
else:
  for i in range(1,N+1):
    count.append(A.count(i))
  count.sort(reverse=True)
  print(N-sum(count[:K]))

### FIXED CODE ###

from collections import deque

N,K = map(int,input().split())
A = list(map(int,input().split()))
nums = [0]*N

for i in range(N):
  nums[A[i]-1] += 1

nums.sort()

nums = deque(nums)

while True:
  if nums[0] == 0:
    nums.popleft()
  else:
    break
nums = list(nums)
if len(nums) <= K:
  print(0)
else:
  print(sum(nums[:len(nums)-K]))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")






    




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
c = []
for i in range(1, n+1):
  c.append(l.index(i) + 1)

[print(s, end=" ") for s in c]


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
c = {}
for i in range(n):
  c[l[i]] = i + 1
c = sorted(c.items())
[print(s[1], end=" ") for s in c]
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0 for i in range(N)]

#iは知りたいdp
for i in range(1,N):
    #for j in range(max(i-K,0),i)はジャンプできる段数
    dp[i] = min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N

#iは知りたいdp[i]
for i in range(1,N):
    #for j in range(max(i-K,0),i)はジャンプできる段数
    dp[i] = min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[N-1])
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    N = int(input())
    D, X = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(N)]

    cnt = 0
    for i in range(N):
        day = 0
        j = 0
        while day <= D:
            day = j * As[i] + 1 
            cnt +=1
    print(cnt)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    N = int(input())
    D, X = [int(item) for item in input().split()]
    As = [int(input()) for _ in range(N)]

    cnt = 0
    for i in range(N):
        day = 1
        while day <= D:
            day +=As[i] 
            cnt +=1

    print(cnt+X)


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

for e in iter(input,'-1'):
 q=float(input())
 x=q/2
 while abs(x**3-q)-q*1e-5:x-=(x**3-q)/(3*x*x)
 print(x)


### FIXED CODE ###

for e in iter(input,'-1'):
 q=float(e)
 x=q/2
 while abs(x**3-q)>=q*1e-5:x-=(x**3-q)/3/x/x
 print(x)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [0]*Q + [10**10]
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

from collections import deque


def bfs(sy, sx):
    t = ((-1,0),(0,-1),(1,0),(0,1))
    dist = [[inf]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while(q):
        y,x = q.popleft()
        d = dist[y][x]
        for i,j in t:
            ny,nx = y+i,x+j
            if (0 <= nx < w and 0 <= ny < h):
                if dist[ny][nx] <= d or s[ny][nx] == "#":
                    continue
                q.appendleft((y+i,x+j))
                dist[ny][nx] = d
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx = y+i,x+j
                if (0 <= nx < w and 0 <= ny < h):
                    if dist[ny][nx] <= d+1 or s[ny][nx] == "#":
                        continue
                    q.append((ny,nx))
                    dist[ny][nx] = d+1
    return dist

inf = 10**9
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
dist = bfs(ch,cw)
ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)

### FIXED CODE ###

from collections import deque


def bfs(sy, sx):
    t = ((-1,0),(0,-1),(1,0),(0,1))
    dist = [[inf]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while(q):
        y,x = q.popleft()
        d = dist[y][x]
        for i,j in t:
            ny,nx = y+i,x+j
            if (0 <= nx < w and 0 <= ny < h):
                if dist[ny][nx] <= d or s[ny][nx] == "#":
                    continue
                q.appendleft((y+i,x+j))
                dist[ny][nx] = d
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx = y+i,x+j
                if (0 <= nx < w and 0 <= ny < h):
                    if dist[ny][nx] <= d+1 or s[ny][nx] == "#":
                        continue
                    q.append((ny,nx))
                    dist[ny][nx] = d+1
    return dist

inf = 10**9
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
dist = bfs(ch,cw)
ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import numpy as np
from numba import njit
n = int(input())
a = np.array(list(map(int,input().split())),np.int32)

@njit
def solve():
    m = np.zeros(10**6 + 1)
    for i in a:
        if m[i] == 1:
            m[i] = 2
            continue
        m[::i] += 1
    ans = 0
    for i in a:
        if m[i] == 1:
            ans += 1
    print(ans)

solve()

### FIXED CODE ###

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

ma = max(a)
m = [0]*(ma + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    for j in range(i,ma+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split(' '))

balls = []

for i in range(10**100):
  for a in range(A):
    if len(balls) < N:
      balls.append('b') 
    else:
      break

  for b in range(B):
    if len(balls) < N:
      balls.append('r')
    else:
      break
      
  if len(balls) >= N:
    break

print(balls[:N].count('b'))

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
 
d = N//(A+B)*A
d+=min(A,N % (A+B))
 
print (d)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

pos = 0

changer = []

for i in range(m):
    b, c = nm()
    changer.append((c, b))

changer = sorted(changer)[::-1]


for i in range(m):
    pos = 0

    c = changer[i]
    for j in range(c[1]):
        while pos < n:
            if a[pos] < c[0]:
                a[pos] = c[0]
                break
            pos += 1

print(sum(a))


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

pos = 0

changer = []

for i in range(m):
    b, c = nm()
    changer.append((c, b))

changer = sorted(changer)[::-1]


for i in range(m):

    c = changer[i]
    for j in range(c[1]):
        while pos < n:
            if a[pos] < c[0]:
                a[pos] = c[0]
                break
            pos += 1
    if pos >= n:
        break

print(sum(a))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            a, b, c = l[i], l[j], l[k]
            if a < b+c and b < c+a and c < a+b:
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
l_copy = l.copy()
l_copy = l_copy[::-1]

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        rest = l_copy[i] - l_copy[j]
        ind = bisect.bisect_right(l, rest)
        ind = n - ind - 1
        if ind <= j:
            break
        else:
            ans += ind - j

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

S = input()
T = input()

count = 0

while S != T:
  for i in range(len(S)):
    if S[i] != T[i]:
      S = S[:i]+T[i]+S[i+1:]
      break
  count += 1
  
print(count)

### FIXED CODE ###

S = input()
T = input()

count = 0

for i in range(len(S)):
    if S[i] != T[i]:
      count += 1
  
print(count)
### BUGGY CODE ###

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

    total = 1

    for i in a :
        if i == 0 :
            print(0)
            return
        total *= i

    if total > 1000000000000000000 :
        print(-1)
        return

    print(total)

if __name__ == "__main__" :
    solve()

### FIXED CODE ###

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

    total = 1

    if 0 in a :
        print(0)
        return

    for i in a :
        total *= i

        if total > 10 ** 18 :
            print(-1)
            return

    print(total)

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

import math

K = int(input())
sumGCD = K * K * K
for a in range(2, K + 1, 1):
    for b in range(2, K + 1, 1):
        for c in range(2, K + 1, 1):
            arr = [a, b, c]
            gcdNum = math.gcd(math.gcd(a, b), c)
            # if gcdNum != 1:
            # print(arr)
            # print(gcdNum)
            sumGCD += gcdNum - 1
print(sumGCD)


### FIXED CODE ###

import math

K = int(input())
sumGCD = K * K * K
for a in range(2, K + 1, 1):
    for b in range(2, K + 1, 1):
        for c in range(2, K + 1, 1):
            arr = [a, b, c]
            gcdNum = math.gcd(math.gcd(a, b), c)
            # if gcdNum != 1:
            # print(arr)
            # print(gcdNum)
            sumGCD += gcdNum - 1
print(sumGCD)
### BUGGY CODE ###

def f(n):
  cnt = 0
  for i in range(int(n**1/2 // 1)):
    for j in range(int(n**1/2 // 1)):
      for k in range(int(n**1/2 // 1)):
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n:
          cnt += 1
  return cnt
      
  
N = int(input())
for i in range(N):
  print(f(i+1))

### FIXED CODE ###

n = int(input())
a = [0]*n
cnt = 0
for i in range(1,100):
  for j in range(1,100):
    for k in range(1,100):
      b = i**2 + j**2 + k**2 + i*j + j*k + k*i
      if b <= n:
        a[b-1] += 1

for i in a:
  print(i)
### BUGGY CODE ###

s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        effect = c*effects[i%6]%13
        amari = [amari[j-effect] for j in range(13)]
    else :
        amari = [sum(amari[j-c*effects[i%6]%13] for c in range(10))%mod \
                                                 for j in range(13)]

print(amari[5])

### FIXED CODE ###

import numpy as np
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
arrays = [np.eye(13, k=i, dtype=np.int64)+np.eye(13, k=i-13, dtype=np.int64) for i in range(13)]
brrays = [sum(arrays[c*effects[i]%13] for c in range(10)) for i in range(6)]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        array = arrays[c*effects[i%6]%13]
        amari = np.dot(amari, array)
    else :
        array = brrays[i%6]
        amari = np.dot(amari, array)%mod

print(amari[5])
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        print(A.count(i+1))
main()

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
bukaninzu_list = N * [0]
for i in range(N-1):
    bukaninzu_list[A[i]-1] += 1

for bukaninzu in bukaninzu_list:    
    print(bukaninzu)
### BUGGY CODE ###

n = int(input())

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

ans = 1

for i in range(n):
    ans *= a[i]

if ans > 10 ** 18:
    ans = -1

print(ans)


### FIXED CODE ###

n = int(input())
a = 1
s = list(map(int, input().split()))
if 0 in s:
    print(0)
    exit()
for i in s:
    a*=i
    if a>10**18:
        print(-1)
        exit()
else:
    print(a)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
def bin_search(key, list):
    ok = n
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if list[mid] > key:
            ok = mid
        else:
            ng = mid
    return ok

ans = 0
for i in range(1, n - 1):
    for j in range(i + 1, n):
        c_min_len = l[j] - l[i]
        x = i - bin_search(c_min_len, l)
        ans += max(0, x)
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
def bin_search(key, list):
    ok = n
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if list[mid] > key:
            ok = mid
        else:
            ng = mid
    return ok

ans = 0
for i in range(1, n - 1):
    for j in range(i + 1, n):
        c_min_len = l[j] - l[i]
        x = i - bin_search(c_min_len, l)
        ans += max(0, x)
print(ans)
### BUGGY CODE ###

import sys

values = [int(input()) for i in range(int(input()))]

maxv = - sys.maxsize - 1

for c, i in enumerate(values):
    for j in values[c + 1:]:
        maxv = max(maxv, j - i)

print(maxv)


### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    for k in range(j+1,n):
      if a[k] >= chk:
        ans += (k-j-1)
        break
      if k == n-1:
        ans += (n-j-1)
print(ans)  

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    ind = bisect.bisect_left(a,chk)
    ans += (ind-j-1)
print(ans)
### BUGGY CODE ###

import sys

# print('input >>')
N = int(input())
As = list(map(int,(input().split())))

INF = 10 ** 18

ans = 1
for A in As:
    ans *= A

if ans > INF:
    ans = -1

# print('-----output-----')
print(ans)


### FIXED CODE ###

import sys

# print('input >>')
N = int(input())
As = list(map(int,(input().split())))

INF = 10 ** 18

ans = 1

over = False

for A in As:
    if A == 0:
        print(0)
        sys.exit()

for A in As:
    ans *= A
    if ans > INF:
        print(-1)
        sys.exit()
        
# print('-----output-----')
print(ans)
### BUGGY CODE ###

from sys import exit, stdin
import copy

# import numpy as np
from collections import deque, Counter

N, Q = map(int, stdin.readline().split())
C = list(map(int, stdin.readline().split()))
R = [list(map(int, stdin.readline().split())) for _ in range(Q)]


tmp = Counter([])

q = [copy.deepcopy(tmp)]

for c in C:
    tmp[str(c)] += 1
    q.append(copy.deepcopy(tmp))

for r in R:
    d = q[r[1]] - q[r[0] - 1]
    print(len(d))


### FIXED CODE ###

# import numpy as np
from sys import exit, stdin
import copy
from collections import deque, Counter


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

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

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            tmp = i[0] + 1
            while tmp:
                x += self.d[tmp]
                tmp -= tmp & (-tmp)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


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

app = [-1] * (N + 1)
ps = [[] for _ in range(N)]
for i in range(N):
    tmp = app[C[i]]
    if tmp != -1:
        ps[tmp].append(i)
    app[C[i]] = i

qs = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, stdin.readline().split())
    l -= 1
    r -= 1
    qs[l].append(copy.deepcopy([r, i]))

ans = [0] * Q
d = BIT(N)
for x in range(N - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    for p in qs[x]:
        r = p[0]
        i = p[1]
        ans[i] = (r - x + 1) - d.sum(r)

for re in ans:
    print(re)