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

from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for i, j in product(range(-2, 3), repeat=2):
            cnt = (abs(i) + abs(j) >= 2)
            i, j = x + i, y + j
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))


### FIXED CODE ###

from collections import deque
from itertools import product


def bfs(S):
    x, y = S
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([S])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for i, j in near_a:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] and s[j][i] == '.'):
                dist[j][i] = dist[y][x]
                que.appendleft((i, j))
        for i, j in near_b:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + 1 and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + 1
                que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs((Cw - 1, Ch - 1))[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)
### BUGGY CODE ###

def enter_card(card, L, R):
    for k in range(L-1,R):
        card[k] += 1
    return card

def open_list(a, M):
    b = []
    for (index, i) in enumerate(a):
        if i == M:
            b.append(index)
    return b

N, M = map(int, input().split(' '))
idcard = [0 for i in range(N)]
for i in range(M):
    L,  R = map(int, input().split(' '))
    idcard = enter_card(idcard, L, R)
a = open_list(idcard, M)
print(len(a))

### FIXED CODE ###

def enter_card(L, R, f_point, e_point):
    if f_point < L:
        f_point = L
    if e_point > R:
        e_point = R
    return f_point, e_point

def open_list(L, R):
    if L > R:
        return 0
    else:
        return R - L + 1
   

N, M = map(int, input().split(' '))
f_point = 1
e_point = N
for i in range(M):
    L,  R = map(int, input().split(' '))
    f_point, e_point = enter_card(L, R, f_point, e_point)
a = open_list(f_point, e_point)
print(a)
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
S = input()

l = [list(np.repeat(0, K)), list(np.repeat(0, K))]
ans = []
k = [int(s) for s in S]
v0 = 1 if k[0] == 0 else 0
v1 = 1 if k[0] == 1 else 0
for i in range(1, N):
    if (k[i]==0) & (k[i-1]==0):
        v0 += 1
    elif (k[i]==1) & (k[i-1]==0):
        l[0].append(v0)
        v0 = 0
        v1 += 1
    elif (k[i]==0) & (k[i-1]==1):
        l[1].append(v1)
        v1 = 0
        v0 += 1
        
        a = sum(l[0][-K:]+l[1][-K-1:])
        ans.append(a)    
    else:
        v1 += 1
        
for i, v in enumerate([v0, v1]):
    if v > 0:
        l[i].append(v)

if len(l[0])-K <= K:
    print(N)

else:
    a = sum(l[0][-K:]+l[1][-K-1:])
    ans.append(a)
    print(max(ans))

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
S = input()

l = [[], []]
ans = []
k = [int(s) for s in S]
if k[0] == 0:
    l[1].append(0)
v0 = 1 if k[0] == 0 else 0
v1 = 1 if k[0] == 1 else 0
for i in range(1, N):
    if (k[i]==0) & (k[i-1]==0):
        v0 += 1
    elif (k[i]==1) & (k[i-1]==0):
        l[0].append(v0)
        v0 = 0
        v1 += 1
    elif (k[i]==0) & (k[i-1]==1):
        l[1].append(v1)
        v0 += 1
        v1 = 0 
    else:
        v1 += 1
        
for i, v in enumerate([v0, v1]):
    if v > 0:
        l[i].append(v)
        
if k[0] == 0:
    l[1].append(0)

if len(l[0]) <= K:
    print(N)

else:
    l[0].extend(np.repeat(0,K+1))
    l[1].extend(np.repeat(0,K+1))
    a = sum(l[0][:K]) + sum(l[1][:K+1])
    ans.append(a)
    for i in range(1, len(l[0])-K-1):
        a -= l[0][i-1] + l[1][i-1]
        a += l[0][i+K-1] + l[1][i+K]
        ans.append(a)
    print(max(ans))
### BUGGY CODE ###

from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].append(b)
        E[b].append(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    cand = {i for i in range(1, K + 1)}

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        c, v = Q.popleft()
        C = cand - {c}
        for u in E[v]:
            if visited[u]:
                continue
            visited[u] = True
            c = C.pop()
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)

    print(K)
    print("\n".join(A))

main()


### FIXED CODE ###

from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [set() for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].add(b)
        E[b].add(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        a, v = Q.popleft()
        c = 0
        for u in E[v]:
            E[u].remove(v)
            c += 1
            if c == a:
                c += 1
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)
        E[v] = set()
    print(K)
    print("\n".join(A))

main()
### BUGGY CODE ###

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

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    for c in str:
        pat ^= 2**(ord(c)-97)
        s[pat] = min(
            min(s.get(pat^2**i, len(str)) + 1 for i in range(26)),
            s.get(pat, len(str)))

    if pat == 0:
        return 1

    return s[pat]
            

def test():
    assert f('aabxyyzz') == 2
    assert f('byebye') == 1
    assert f('abcdefghijklmnopqrstuvwxyz') == 26
    assert f('abcabcxabcx') == 3


def main():
    str = input()
    print(f(str))


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    bits = [2**i for i in range(26)]
    lenOfStr = len(str)

    for c in str:
        pat ^= bits[ord(c)-97]
        s[pat] = min(
            min(s.get(pat^bit, lenOfStr) + 1 for bit in bits),
            s.get(pat, lenOfStr))

    if pat == 0:
        return 1

    return s[pat]
            
str = input()
print(f(str))
### BUGGY CODE ###

a,b,n = map(int,input().split())
for i in range(n+1):
    c = int(a*i/b)-a*int(i/b)
    if i == 0:
        d = c
    else:
        if c > d:
            d = c
print(d)

### FIXED CODE ###

a,b,n = map(int,input().split())
if n>= b-1:
    print(int(a*(b-1)/b)-a*int((b-1)/b))
else:
    print(int(a*n/b)-a*int(n/b))
### BUGGY CODE ###

def e_flatten_prime_factorization(MOD=10**9 + 7):
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    lcm_prime = defaultdict(int)
    for a in A:
        for base, exp in prime_factorization_dict(a).items():
            lcm_prime[base] = max(lcm_prime[base], exp)
    lcm = 1
    for base, exp in lcm_prime.items():
        lcm *= pow(base, exp, MOD)
        lcm %= MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten_prime_factorization())


### FIXED CODE ###

def e_flatten(MOD=10**9 + 7):
    from fractions import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

    def lcm(a, b):
        return a * b // gcd(a, b)

    def inv(n, mod=MOD):
        return pow(n, mod - 2, mod)

    l = reduce(lcm, A) % MOD
    ans = [(l * inv(a)) % MOD for a in A]
    return sum(ans) % MOD

print(e_flatten())
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [0] * H
for i in range(H):
  maze[i] = str(input())
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
q = deque([[0, Ch, Cw]])  
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i in [-2, -1, 0, 1, 2]:
    for j in [-2, -1, 0, 1, 2]:
      if (0 <= h + i < H) and (0 <= w + j < W):
        if i== 0 and j == 0:
          continue
        elif abs(i) + abs(j) == 1:
          if maze[h + i][w + j] == ".":
            if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
              ans[h + i][w + j] = cnt
              q.appendleft([cnt, h + i, w + j])
        else:
          if maze[h + i][w + j] == ".":
            if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
              ans[h + i][w + j] = cnt + 1
              q.appendleft([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])              
          
              
          
          
    
    
    

  


### FIXED CODE ###


H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
maze = [list(input()) for i in range(H)]
#print(maze)
  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
from collections import deque
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "#"):
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.append([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])
### BUGGY CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx != ry):
            self.par = [ry if i == rx else i for i in self.par]

def output(uf):
    count = 0
    for i in range(uf.N):
        sub_par = uf.par[i+1:]
        count += len(sub_par) - sub_par.count(uf.par[i])

    return count



n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [output(uf)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    if not uf.same(a,b):
        uf.unite(a,b)
        result.append(output(uf))
    else:
        result.append(result[-1])

for i in result[::-1][1:]:
    print(i)

#print(uf.par)


### FIXED CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]

n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [int(n*(n-1)/2)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    if not uf.same(a,b):
        x = uf.size[uf.root(a)] * uf.size[uf.root(b)]
        uf.unite(a,b)
        result.append(int(result[-1]-x))
    else:
        result.append(result[-1])

for i in result[::-1][1:]:
    print(i)

#print(uf.par)
### BUGGY CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    s = input()
    q = int(input())
    ans = deque()
    swap = False
    for i in range(len(s)):
        ans.append(s[i])

    for i in range(q):
        #print(ans, swap)
        inp = input()
        if len(inp) == 1:
            hoge = int(inp)
            if swap:
                swap = False
            else:
                swap = True
        else:
            # print(tuple(inp))
            fi, ci = tuple(inp)[2], tuple(inp)[4]
                       
            if int(fi) == 1:
                if not swap:
                    ans.appendleft(ci)
                else:
                    ans.append(ci)
            if int(fi) == 2:
                if not swap:
                    ans.append(ci)
                else:
                    ans.appendleft(ci)
    if swap:
        ans = list(ans)[::-1]
    else:
        ans = list(ans)
    s_ans = str()
    for i in range(len(ans)):
        s_ans += ans[i]
    print(s_ans)
                
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    s = input()
    q = int(input())
    ans = deque()
    swap = False
    for i in range(len(s)):
        ans.append(s[i])

    for i in range(q):
        #print(ans, swap)
        inp = input()
        if len(inp) == 1:
            hoge = int(inp)
            if swap:
                swap = False
            else:
                swap = True
        else:
            # print(tuple(inp))
            fi, ci = tuple(inp)[2], tuple(inp)[4]
                       
            if int(fi) == 1:
                if not swap:
                    ans.appendleft(ci)
                else:
                    ans.append(ci)
            if int(fi) == 2:
                if not swap:
                    ans.append(ci)
                else:
                    ans.appendleft(ci)
    s_ans = str()
    ans = list(ans)
    if swap:
        for i in range(len(ans)-1,-1, -1):
            s_ans += ans[i]
    else:
        for i in range(len(ans)):
            s_ans += ans[i]
    
    print(s_ans)
                
    return

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

S = input()
T = input()

dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

### FIXED CODE ###

S = input()
T = input()
dp = [[ 0] * (len(S) + 1 ) for _ in range(len(T) + 1)]
ma = 0
for i in range(len(dp)-1):
    for j in range(len(dp[0])-1):
        if T[i ] == S[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
             dp[i + 1][j + 1]  = max(dp[i][j + 1],dp[i +1][j])
i = len(T) - 1
j = len(S) - 1 
ans = ""
while i >=0 and j >= 0:
    if dp[i][j+1] == dp[i + 1][j + 1]:
        i-=1
    elif dp[i + 1][j] == dp[i + 1][j + 1]:
        j-=1
    else:
        #print(j,i)
        ans = S[j] + ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

from collections import deque


def pprint():
    [print(row) for row in field]


def bfs(start):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == (H - 1, W - 1):
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if (
                0 <= ni < H
                and 0 <= nj < W
                and field[ni][nj] != "#"
                and (ni, nj) not in visited
            ):
                new_path = list(path) + [(ni, nj)]
                q.append(new_path)
            visited.add((i, j))


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0))
if shortest_path is None:
    print(-1)
    exit()
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == "." and (i, j) not in shortest_path:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import deque


def bfs(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in visited:
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' and (i, j) not in path for i in range(H) for j in range(W)))
else:
    print(-1)
### BUGGY CODE ###

l, r = list(map(int, input().split()))
ans = r*r
for i in range(l, r):
    for j in range(i+1, r+1):
        ans = min(ans, (i*j)%2019)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
    
ans = 2019
for i in range(L, min(L+2019, R),1):
    for j in range(i+1, min(L+2019, R)+1,1):
        ans = min(ans, (i*j)%2019)

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

n = int(input())
p = list(map(int, input().split()))
count = 0

for i in range(n):
  flag = True
  for j in range(i):
    if p[i] > p[j]:
      flag = False
  if flag:
    count+=1
print(count)
    

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
minP = p[0]
for i in range(n):
  minP = p[i] if minP > p[i] else minP
  if p[i] <= minP:
    count+=1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
memo = [0] * (10**6 + 1)
for i in a:
    for j in range(i, 10**6+1, i):
        memo[j] += 1

ans = 0
for i in a:
    if memo[i] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()

cnt = [0]*(10**6 + 1)
lst = [True]*(10**6+1)
for i in a:
    cnt[i] += 1

ans = 0
for i in a:
    if cnt[i] == 1 and lst[i]:
        ans += 1
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1
    elif lst[i]:
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1

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

N = input()
A = tuple(map(int,input().split()))
N = 1
for i in range(len(A)):
    N *= A[i]

if N <= 10**18:
    print(N)
else:
    print(-1)

### FIXED CODE ###

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

if 0 in A :
    print(0)
    exit()
for i in A:
    m*= i
    if m > 10**18:
        print(-1)
        exit()
print(m)
### BUGGY CODE ###

from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


def add(arr, i, x):
    while i < len(arr):
        arr[i] += x
        i += i & -i


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            add(bit, li, -1)
        last[ci] = i + 1
        add(bit, i + 1, 1)
        while i + 1 == r:
            ans[k] = range_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

    def add(self, i, x):
        if not i > 0:
            return
        while i < self.size:
            self.array[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.array[i]
            i -= i & -i
        return s


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            bit.add(last[ci], -1)
            last[ci] = ri + 1
            bit.add(last[ci], 1)
            cr = ri
        ans[i] = bit.sum(r) - bit.sum(l - 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()