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

n = int(input())
a =list(map(int,input().split()))
s = 1
f = 0
if not a.count(0) == 0:
  print ("0")
  f += 1
if f == 0:
  for _ in range(n):
    s *= a[_]
  if len(str(s-1)) > 18:
    print("-1")
    f += 1
if f == 0:
  print(s)

### FIXED CODE ###

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

def binarySearch(x, S):
    mid = len(S) / 2
    if mid < 2:
        return x in S
    if S[mid] == x:
        return True
    elif S[mid] > x:
        return binarySearch(x, S[:mid])
    else:
        return binarySearch(x, S[mid+1:])

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
    if binarySearch(x, S):
        count += 1
print count

### FIXED CODE ###

def binarySearch(x, S):
    left = 0
    right = len(S)
    while left < right:
        mid = (left + right) / 2
        if x == S[mid]:
            return mid
        elif x < S[mid]:
            right = mid
        else:
            left = mid + 1
    return -1

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
    if binarySearch(x, S) >= 0:
        count += 1
print count
### BUGGY CODE ###

def main():
    n = int(input())
    a = input().split()

    maks = 10**18
    mnozenje = 1
    for i in a:
        mnozenje *= int(i)

    if mnozenje > maks:
        print(-1)
    else:
        print(mnozenje)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    if 0 in a:
        print(0)
        return

    maks = 10**18
    mnozenje = 1
    for i in a:
        mnozenje *= i

        if mnozenje > maks:
            print(-1)
            return

    print(mnozenje)


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

import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
As = list(map(int, input().split()))
table = [0] * (10 ** 6 + 1)
ans = n
for a in As:
    tmp = a
    table[tmp] += 1
    for _ in range((10 ** 6) // a - 1):
        tmp += a
        table[tmp] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)


### FIXED CODE ###

import numpy as np
import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
As = list(map(int, input().split()))
ans = n
val = 10 ** 6
table = np.array([0] * (val + 1))
for a in As:
    if table[a] > 1:
        continue
    table[::a] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)
### BUGGY CODE ###

N = int(input())
lst = []
for _ in range(N):
    s = input()
    if not s in lst:
        lst.append(s)
print(len(lst))

### FIXED CODE ###

N = int(input())
S = set()
count = 0
for _ in range(N):
    s = input()
    S.add(s)
print(len(S))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
import heapq
def bfs(start_set):
  que = []
  for si,sj in start_set:
    que.append((0,si,sj))
    dis[si][sj] = 0
  while que:
    cost,i,j = heapq.heappop(que)
    if dis[i][j] < cost: continue
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "#":continue
      # if A[ni][nj] == "#" and dis[ni][nj] == inf:
      #   dis[ni][nj] = 0
      #   heapq.heappush(que,(0,ni,nj))
      if cost + 1 < dis[ni][nj]: 
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))

start_set = []
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      start_set.append((i,j))
bfs(start_set)
      
print(max(map(max,dis)))





### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)
### BUGGY CODE ###

#!/usr/bin/env python3
import io
import os


def main():
    buffer = map(int, os.read(0, os.fstat(0).st_size).split())
    n, m = next(buffer), next(buffer)
    dp = [0] * (m + 1)
    wi, vi = next(buffer), next(buffer)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = next(buffer), next(buffer)
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-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(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
info = []
ans = []
for i in range(n):
    info.append([a[i], i+1])
# print(info)
info.sort()
for s, o in info:
    print(o)
### BUGGY CODE ###

N, L = map(int, input().split())
A = list(map(int, input().split()))
d = [A[i] + A[i+1] for i in range(N-1)]
if max(d) < L:
  print("Impossible")
else:
  print("Possible")
  j = 0
  while d[j] != max(d):
    j += 1
  for i in range(j):
    print(i+1)
  for i in range(j, N-1):
    print(N-i+j-1)

### FIXED CODE ###

N, L = map(int, input().split())
A = list(map(int, input().split()))
d = [A[i] + A[i+1] for i in range(N-1)]
if max(d) < L:
  print("Impossible")
else:
  print("Possible")
  j = 0
  while d[j] < L:
    j += 1
  for i in range(j):
    print(i+1)
  for i in range(j, N-1):
    print(N-i+j-1)
### BUGGY CODE ###

import math
import copy
N = int(input())
ans = 1
for i in range(2, N // 2 + 1):
    n = copy.deepcopy(N)
    while n >= i:
        if (n % i == 0):
            n = n // i
        else:
            n = n % i
        if n == 1:
            ans += 1
if N // 2 + 1 < N - 1:
    ans += 1
print(ans)

### FIXED CODE ###

import math
import copy
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
if N > 2:
    print(ans)
else:
    print(1)
### BUGGY CODE ###

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


condition = [list(map(str, input().split())) for i in range(Q)]

for i in range(Q):
    if condition[i][0] == '1':
        S = ''.join(list(reversed(S)))
    elif condition[i][0] == '2':
        if condition[i][1] == '1':
            S = condition[i][2] + S
        elif condition[i][1] == '2':
            S = S + condition[i][2]

print(S)


### FIXED CODE ###

from collections import deque
d = deque()

S = input()
Q = int(input())
d.extend(S)




front = True

for i in range(Q):
    inp = input().split()
    if inp[0] == '1':
        front = not front
    else:
        F = int(inp[1])
        C = inp[2]
        if F == 1:
            if front:
                d.appendleft(C)
            else:
                d.append(C)
        elif F == 2:
            if front:
                d.append(C)
            else:
                d.appendleft(C)

if not front:
    d.reverse()

d_list = list(d)
str = "".join(d_list)

print(str)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
tmp = 0
for i in reversed(range(1,M+1)):
    count = 0
    memo = 0
    for j in range(N):
        if A[j]%i != 0:
            count += 1
            memo = j
            if count > 1:
                break
    if count <= 1:
        tmp = i
        break
print(tmp)




### FIXED CODE ###

def gcd(a,b):
    if a <= b:
        a,b = b,a
    if b == 0:
        return a
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

L_gcd = [0]*(N+1)
R_gcd = [0]*(N+1)

for i in range(N):
    L_gcd[i+1] = gcd(L_gcd[i],A[i])
    R_gcd[N-i-1] = gcd(R_gcd[N-i],A[N-i-1])

ans = 0
for i in range(N):
    if gcd(L_gcd[i],R_gcd[i+1])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+1])
    
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
for i in range(M):
    b, c = map(int, input().split())
    A += [c] * b
A.sort()
A.reverse()
print(sum(A[0:N]))


### FIXED CODE ###

import operator as op

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
BC = []
for i in range(M):
    b, c = map(int, input().split())
    BC.append([b, c])
for a in A:
    BC.append([1, a])
BC_sort = sorted(BC, key=op.itemgetter(1), reverse=True)
rest = N
ans = 0
for i in range(len(BC_sort)):
    if rest >= BC_sort[i][0]:
        ans += BC_sort[i][0] * BC_sort[i][1]
        rest -= BC_sort[i][0]
    elif 0 <= rest < BC_sort[i][0]:
        ans += rest * BC_sort[i][1]
        break
print(ans)
### BUGGY CODE ###

N = int(input())
x = list(int(i) for i in input().split())
for i in range(N):
    a = x.pop(i)
    print(sorted(x)[int(N/2-1)])
    x.insert(i,a)
    


### FIXED CODE ###

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

X = []
for i, a in enumerate(A):
    X.append([a, i])

X.sort()

# Biになり得るのはX[m-1] or X[m] (m=N//2)
m = N//2
itoj = {}
for j in range(N):
    x, i = X[j]
    itoj[i] = j
for i in range(N):
    j = itoj[i]
    if j < m:
        print(X[m][0])
    else:
        print(X[m-1][0])
### BUGGY CODE ###

# D - Blue and Red Balls

# 青いボールを並べる→赤いボールを青いボールの間に挿入する→残りの赤いボールを両端に置く

from math import factorial

N, K = map(int, input().split())
MOD = 10**9 + 7

def combinations(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

# 連続した同色のボールの数nと、それらを何分割するか示すaを与えると、分割のパターン数を返す関数
def separate_balls(n,a):
    return combinations(n-1, a-1)

ans_list = []
for i in range(1,K+1):
    if N-K < i-1: # 赤いボール不足でi分割不可
        ans_list.append(0)
    elif i == 1:
        ans_list.append(N-K+1)
    else:
        tmp_blue = separate_balls(K, i) % MOD  # K個の青いボールをi分割するパターン数
        tmp_red = 0
        for j in range(i-1, N-K+1): # 青いボールの分割に使う赤いボールの個数
            tmp_red_inner = separate_balls(j, i-1)  # j個の赤いボールをi-1分割して青いボールの隙間に入れるパターン数
            tmp_red_side = N-K-j+1 # N-K-j個の赤いボールを両端に置くパターン数
            tmp_red += (tmp_red_inner * tmp_red_side) % MOD
        ans_list.append((tmp_blue * tmp_red) % MOD)  # 青いボールの置き方*赤いボールの置き方

for x in ans_list:
    print(x)


### FIXED CODE ###

# D - Blue and Red Balls

# 青いボールを並べる→赤いボールを青いボールの間に挿入する→残りの赤いボールを両端に置く

N, K = map(int, input().split())
MOD = 10**9 + 7

# nCkを漸化式で求め、メモしておく
combinations_table = [[0]*(N+1) for _ in range(N+1)]
for idx in range(N+1):
    combinations_table[0][idx] = 1
    combinations_table[idx][0] = 1
    combinations_table[idx][1] = idx
for n in range(2, N+1):
    for k in range(2, n+1):
        combinations_table[n][k] = combinations_table[n-1][k-1] + combinations_table[n-1][k]

# 連続した同色のボールの数nと、それらを何分割するか示すaを与えると、分割のパターン数を返す関数
def separate_balls(n,a):
    return combinations_table[n-1][a-1]

ans_list = []
for n_separate in range(1,K+1):
    if N-K < n_separate-1: # 赤いボール不足でi分割不可
        ans_list.append(0)
    elif n_separate == 1:
        ans_list.append(N-K+1)
    else:
        tmp_blue = separate_balls(K, n_separate) % MOD  # K個の青いボールをi分割するパターン数
        tmp_red = 0
        for n_red_ball in range(n_separate-1, N-K+1): # 青いボールの分割に使う赤いボールの個数
            tmp_red_inner = separate_balls(n_red_ball, n_separate-1)  # j個の赤いボールをi-1分割して青いボールの隙間に入れるパターン数
            tmp_red_side = N-K-n_red_ball+1 # N-K-j個の赤いボールを両端に置くパターン数
            tmp_red += (tmp_red_inner * tmp_red_side) % MOD
        ans_list.append((tmp_blue * tmp_red) % MOD)  # 青いボールの置き方*赤いボールの置き方

for x in ans_list:
    print(x)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
    if a>=1:
        a-=1
    elif b>=1:
        b-=1
l=[]
l.append(a)
l.append(b)
print(' '.join(map(str, l)))

### FIXED CODE ###

a,b,k=map(int,input().split())
if a-k<1:
    if b-(k-a)>=1: 
        print(0,b-(k-a))
    else:
        print(0,0)
else:
    print(a-k,b)
### BUGGY CODE ###

N = int(input())
T = []
A = []
for i in range(N):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)
    
v1 = T[0]
v2 = A[0]

for i in range(1, N):
    n = 1
    if v1<=T[i] and v2<=A[i]:
        v1 = T[i]
        v2 = A[i]
    else:
        while v1>n*T[i] or v2>n*A[i]:
            n += 1
        v1 = T[i]*n
        v2 = A[i]*n

print(v1+v2) 

### FIXED CODE ###

N = int(input())
T = []
A = []
for i in range(N):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)
    
v1 = 1
v2 = 1

for i in range(N):
    n = max((v1+T[i]-1)//T[i],(v2+A[i]-1)//A[i])
    v1 = T[i]*n
    v2 = A[i]*n

print(v1+v2)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
#     print("i",i)
    for j in range(i+1, N+1):
#         print("j",j)
#         print((i + j) == N)
        if (i + j) == N:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
if N % 2 == 1:
    N += 1
ans = (N/2)-1
print(int(ans))
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited,check_visited,d):
  if visited[v]==True:
    return -1,visited
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited,[False]*ls,[-1]*ls)
    if tmp>ans:
      ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
    for k in range(i):
        if S[k] == S[i]:
            A -= 1
            break
print(A)


### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
### BUGGY CODE ###

def Yes():
  print("Yes")
def No():
  print("No")

def gcd(x, y):
  n = min(x, y)
  for i in range(n, 0, -1):
    if x % i == 0 and y % i == 0:
      return i

def lcm(x, y):
  return (x * y) // gcd(x,y)

def main():
  T = int(input())
  AD = [list(map(int, input().split())) for i in range(T)]

  for i in AD:
    A = i[0]
    B = i[1]
    C = i[2]
    D = i[3]
    if A < B:
      No()
      continue
    if B > D:
      No()
      continue
    add = D - B
    d = gcd(B, D)
    
    C += 1
    t = C % d
    k = A % d
    if k == t:
      LD = C
    elif k > t:
      LD = C + k - t
    else:
      LD = C + d - t + k
    if LD < B:
      No()
    else:
      Yes()

main()

### FIXED CODE ###

def Yes():
  print("Yes")
def No():
  print("No")

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

def main():
  T = int(input())
  AD = [list(map(int, input().split())) for i in range(T)]

  for i in AD:
    A = i[0]
    B = i[1]
    C = i[2]
    D = i[3]
    if A < B:
      No()
      continue
    if B > D:
      No()
      continue
    add = D - B
    d = gcd(B, D)
    
    C += 1
    t = C % d
    k = A % d
    if k == t:
      LD = C
    elif k > t:
      LD = C + k - t
    else:
      LD = C + d - t + k
    if LD < B:
      No()
    else:
      Yes()

main()
### BUGGY CODE ###

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

I = [[] for _ in range(N)] #各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [0 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c+1 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [(tuple(map(lambda a: int(a)-1, input().split())), i) for i in range(Q)] #クエリ
S.sort(key = lambda a: (a[0][1], a[0][0])) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  while S and S[-1][0][1] == j:#クエリへの返答
    s = S.pop()
    ans[s[1]] = BIT_query(s[0][1]+1) - BIT_query(s[0][0])
  
  if not S:
    break
    
  if loc[j] > 0: #最右端の玉である場合
    c = loc[j]-1
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c+1
       
for a in ans:
  print(a)


### FIXED CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')