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

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)

### FIXED CODE ###

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

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


N, K = map(int, input().split())
H = sorted([int(input()) for _ in range(N)])

ans = float("inf")
for i in range(N-K+1):
  t = H[i:i+K]
  ans = min(ans, max(t)-min(t))
print(ans)

### FIXED CODE ###


N, K = map(int, input().split())
H = [int(input())  for i in range(N)]

H = sorted(H)
ans = 999999999999999999999
for i in range(N-K+1):
  ans = min(ans, H[i+K-1] - H[i])

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

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

mod = 10**9 + 7
a = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        a += A[i] * A[j]
        a %= mod
print(a)


### FIXED CODE ###

mod = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]
S = sum(A) % mod

ans = 0
for i in range(N):
    S -= A[i]
    if S < 0: S += mod

    ans += S * A[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

n,a,b = map(int,input().split())
blue = ''.join(['b' for i in range(a)])
red = ''.join(['r' for i in range(b)])
s = str()
while len(s) < n:
    s += blue + red
    
print(s[:n].count('b'))

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = int(n / (a + b))
rem = n % (a + b)
if rem > a:
    print(ans * a + a)
else:
    print(ans * a + rem)
### BUGGY CODE ###

H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

current_list = [(0, 0)]
count = 1
 
while C[H-1][W-1] == '.' or count >= 3000:
    count += 1
    next_list = []
    for y,x in current_list:
        for i,j in ((1,0),(0,1),):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    current_list = list(set(next_list))
if count >= 3000:
    print(-1)
else:
    print(H*W-pre-count)

### FIXED CODE ###

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

# bfs 
C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.' and len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list

if C[H-1][W-1] == '.':
    print(-1)
else:
    black = 0
    for h in C:
        for v in h:
            if v == "#":
                black += 1
    print(H*W-black-count-1)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = []
    cnt = 0
    for _ in range(N):
        n = int(input())
        check = True
        for i, a in enumerate(A):
            if n > a:
                A[i] = n
                check = False
                break

        if check:
            A.append(n)
            cnt += 1

    return cnt


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


### FIXED CODE ###

import sys
from collections import deque
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    a = int(input())
    q = deque()
    q.append(a)
    ans = 1
    for _ in range(N-1):
        n = int(input())
        if n <= q[0]:
            q.appendleft(n)
            ans += 1
            continue

        if n > q[-1]:
            q[-1] = n
            continue

        pos = bisect_left(q, n)
        q[pos-1] = n
        min_ = q[0]

    return ans


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

import copy
x = int(input())

candidates = [0]

for i in range(1, x + 1):
    # print(candidates)
    new_candidates = []
    for c in copy.deepcopy(candidates):
        new_candidates.append(c)
        new_candidates.append(c+i)
        new_candidates.append(c-i)

    if x in new_candidates:
        print(i)
        break

    candidates = copy.deepcopy(new_candidates)


### FIXED CODE ###

import copy
x = int(input())

m = 0

for i in range(1, x + 1):
    m += i
    if x <= m:
        print(i)
        break
### BUGGY CODE ###

s=input()
k=int(input())
l=[i for i in s]
ans=[i for i in s]
mae=[]
for i in range(len(s)-1):
  for j in range(len(l)-1):
    nlen=i+1
    lj=l[j+1]
    now=l[j]+lj[nlen-1:]
    mae.append(now)

  ans.extend(mae)
  l=mae
  mae=[]

ans=list(set(ans))
ans.sort()
print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,min(k+i+1,len(s)+1)):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

N,K = map(int,input().split())
list1 = []
for i in range(N):
    list1.append(list(map(int,input().split())))
list1.sort()
list2 = []
for j in range(N):
    list2 += [list1[j][0]]*list1[j][1]
    if len(list2) >= K:
        break
print(list2[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
list1 = []
for i in range(N):
    list1.append(list(map(int,input().split())))
num = [0]*(10**5+1)
for j in range(N):
    num[list1[j][0]] += list1[j][1]
c = 0
d = 0
for k in range(10**5+1):
    c += num[k]
    if c >= K:
        d = k
        break
print(d)
### BUGGY CODE ###

N, M = map(int,input().split())
a = M // N
x = 1

for i in range(1, a + 1):
    if M % i == 0:
        x = i

print(x)

### FIXED CODE ###

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

for i in range(1, a + 1):
    if m % i == 0:
        ans = i
        
        if (m // i) > i and (m // i) <= a:
            ans = m // i
            break
        
print(ans)
### BUGGY CODE ###

import numpy as np

n=int(input())
a=[]
for i in range(n):
  a.append(str(input()))

a=sorted(a)
b=[]
c=[]

tmp="."
count=0

for i in range(n):
  if tmp != a[i]:
    b.append(tmp)
    c.append(count)
    tmp=a[i]
    count=1
  else:
    count += 1
 
b.append(tmp)
c.append(count)

for i in range(len(b)):
  if c[i]==np.max(c):
    print(b[i])

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(str(input()))

a=sorted(a)
b=[]
c=[]

tmp="."
count=0

for i in range(n):
  if tmp != a[i]:
    b.append(tmp)
    c.append(count)
    tmp=a[i]
    count=1
  else:
    count += 1
 
b.append(tmp)
c.append(count)
k=sorted(c)[-1]
for i in range(len(b)):
  if c[i]==k:
    print(b[i])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

A = {}
for i in range(n):
  A = dict(Counter(A) + Counter({a[i]:1}))

def sumA(A):
  ans = 0
  for x in A.keys():
    ans += x * A[x]
  return ans

q = int(input())
for i in range(q):
  b,c = list(map(int, input().split()))
  if b in A.keys():
    A = dict(Counter(A) + Counter({c:A[b]}))
    A = dict(Counter(A) - Counter({b:A[b]}))
  print(sumA(A))


### FIXED CODE ###

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

A = [0] * 100001
for i in a:
  A[i] += 1

ans  = 0
for i in range(len(A)):
  ans += i * A[i]  

for n in range(q):
  b,c = list(map(int, input().split()))
  ans += (c * A[b]) - (b * A[b])
  A[c] += A[b]
  A[b] = 0
  print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

for x in a:
  cnt = 0
  for i in range(x[0]-1, x[1]-1):
    if s[i:i+2] == 'AC':
      cnt += 1
  print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

c = [0] * n
for i in range(1,n):
  c[i] = c[i-1] + (s[i-1]+s[i] == 'AC')

for x in a:
  print(c[x[1]-1]-c[x[0]-1])
### BUGGY CODE ###

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

for i in range(m):
    a,b=[int(i) for i in input().split()]
    for j in range(a):
        List.append(b)
    List.sort()
    List=List[-n:]
#print(List)
print(sum(List[-n:]))


### FIXED CODE ###

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

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))
### BUGGY CODE ###

n = int(input())
m = 0


for i in range(n):
    t = i + 1
    if t == n:
        m += 0
    else:
        m += t % (t + 1)


print(m)


### FIXED CODE ###

n = int(input())

m = n * (n - 1) // 2

print(m)
### BUGGY CODE ###

print(sum(range(1, int(input()))))

### FIXED CODE ###

n = int(input())
print((n - 1) * n // 2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)
### BUGGY CODE ###

N = int(input())
i = 1
count = 0
if N <= 777777777:
    while i <= N:
        I = str(i)
        I = list(I)
        if I.count("3")>0 and I.count("5")>0 and I.count("7"):
            if I.count("0")==0 and I.count("1")==0 and I.count("2")==0 and I.count("4")==0 and I.count("6")==0 and I.count("8")==0 and I.count("9")==0:
                count+=1
                i+=1
            else:
                i+=1
        else:
            i+=1
    print(count)
else:
    print(26484)

### FIXED CODE ###

N = int(input())
def shichi(n):
    if int(n) > N:
        return 0
    ret=1 if all(n.count(c)>0 for c in "753") else 0
    for c in "753":
        ret += shichi(n+c)
    return ret
print(shichi("0"))
### BUGGY CODE ###

S=input()
for i in range(1,10):
    s = "S"*i +"T"*i
    while s in S:
        S=S.replace(s,"")
print(len(S))

### FIXED CODE ###

from collections import deque
S=list(map(lambda x: 1 if x=="T" else 0,input()))

q=deque()

for i in S:

    if i:
        if (not q) or q[-1]!=0:
            q.append(i)
        elif q and q[-1]==0:
            q.pop()
    else:
        q.append(i)
print(len(q))
### BUGGY CODE ###

def main():
    N = int(input())
    a = [0 for i in range(N)]
    for i in range(N):
        a[i] = int(input())
    d = [1]
    ans = 0
    for i in range(N):
        if a[d[i]-1] == 2:
            ans += 1
            break
        elif a[d[i]-1] in d or i == N - 1:
            ans = -1
            break
        else:
            d.append(a[d[i]-1])
            ans += 1
    print(ans)
main()



### FIXED CODE ###

def main():
    N = int(input())
    a = [0 for i in range(N)]
    for i in range(N):
        a[i] = int(input())
    now = 1
    for i in range(N):
        if a[now - 1] == 2:
            break
        elif i == N - 1:
            i = -2
        else:
            now = a[now - 1]
        #print('{}: {}'.format(i, now))
    print(i + 1)
main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    if i%2==1:
        b=[a[i]]+b
    else:
        b.append(a[i])
if n%2==0:
    print(*b)
else:
    print(*b[::-1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=a[1::2][::-1]+a[::2]
if n%2==0:
    print(*b)
else:
    print(*b[::-1])
### BUGGY CODE ###

N = int(input())
S = input().strip()

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

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if i >= j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min([dp[i][j], j-1])
        ans = max(ans, now)

print(ans)


### FIXED CODE ###

N = int(input())
S = input().strip()

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

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if i >= j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min([dp[i][j], j-i])
        ans = max(ans, now)

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

import sys
input = lambda: sys.stdin.readline().rstrip()

def solve(a):
    a_max = max(a)
    idx_max = a.index(a_max)
    return ((len(a) - 1 - idx_max) * a_max) - sum(a[idx_max + 1:]), idx_max

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    while(1):
        k, idx_max = solve(a)
        ans += k
        a = a[:idx_max]
        if idx_max == 0:
            break
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    idx_start = 0
    sum_a = 0
    ans = 0
    cnt = 0
    len_a = len(a)

    for i in range(1, len_a):
        if a[idx_start] < a[i]:
            ans += (cnt * a[idx_start]) - sum_a
            idx_start = i
            sum_a = 0
            cnt = 0
        else:
            sum_a += a[i]
            cnt += 1
            if i == len_a - 1:
                ans += (cnt * a[idx_start]) - sum_a
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

a_fac = []
lcm_fac = defaultdict(int)
for i in range(n):
    a_fac.append(factorize(a[i]))
    for k, v in a_fac[i].items():
        lcm_fac[k] = max(lcm_fac[k], v)

# print(lcm_fac)
ans = 0
for i in range(n):
    b_i = 1
    for k, v in lcm_fac.items():
        b_i *= pow(k, v - a_fac[i][k], MOD)
        b_i %= MOD
    # print(i, a[i], b_i)
    ans += b_i
    ans %= MOD

print(ans)


### FIXED CODE ###

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

lcm = 1
for i in range(n):
    lcm = LCM(lcm, a[i])

lcm %= MOD

ans = 0
for i in range(n):
    ans += lcm * iinv[a[i]]
    ans %= MOD

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

def main():
  import sys
  input = sys.stdin.readline
  s = input()
  s = s.rstrip('\r\n')
  q = int(input())
  c = [[i for i in input().split()] for j in range(q)]

  for i in c:
    if i[0] == '1':
      s = s[::-1]
    else:
      if i[1] == '1':
        s = i[2] + s
      else:
        s = s + i[2]
  print(s)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  s = list(input())
  s = s[:-1]
  s = deque(s)
  q = int(input())
  c = [[i for i in input().split()] for j in range(q)]
  cnt = 1
  for i in c:
    if i[0] == '1':
      cnt *= -1
    else:
      if (i[1] == '1' and cnt == 1) or (i[1] == '2' and cnt == -1):
        s.appendleft(i[2])
      else:
        s.append(i[2])
  if cnt == 1:
    print(''.join(s))
  else:
    print(''.join(s)[::-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = input()
a = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
cnt = 0
tmp_i = -1
tmp_j = -1
for num in a:
    for i in range(N):
        if S[i]==num[0]:
            tmp_i = i
            break
    if tmp_i == -1:
        continue
    for j in range(N-1,-1,-1):
        if S[j]==num[2]:
            tmp_j = j
            break
    if tmp_j == -1:
        tmp_i = -1
        continue
    if tmp_i+1<tmp_j:
        if num[1] in S[tmp_i+1:tmp_j]:
            cnt+=1
    tmp_i = -1
    tmp_j = -1
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

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

import sys
from collections import deque
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[0]*(n+1)
    chk=[(1,0)]
    while chk:
        x,d=chk.pop()
        for v,w in l[x]:
            chk.append((v,d+w))
            if (d+w)%2==0:
                ans[v]=0
            else:
                ans[v]=1
    [print(i) for i in ans[1:]]

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n=int(input())
    l=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,input().split())
        u-=1
        v-=1
        l[u].append([v,w])
        l[v].append([u,w])
    ans=[-1]*n
    chk=[(0,0,-1)]
    while chk:
        v,d,p=chk.pop()
        if d%2==0:
            ans[v]=0
        else:
            ans[v]=1
        for u,w in l[v]:
            if u==p:
                continue
            chk.append((u,d+w,v))
    [print(i) for i in ans]

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

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    sq = int(n ** .5)
    g = [0]*q
    for i in range(q):
        l, r = nm()
        gr = l // sq
        g[i] = (gr << 60) + ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    d = [0]*(n+1)
    cl = 0; cr = -1
    cur = 0
    for x in g:
        i = x & mask
        x >>= 20
        l = x & mask
        x >>= 20
        r = x & mask
        while r > cr:
            cr += 1
            if d[c[cr]] == 0:
                cur += 1
            d[c[cr]] += 1
        while l < cl:
            cl -= 1
            if d[c[cl]] == 0:
                cur += 1
            d[c[cl]] += 1
        while cr > r:
            if d[c[cr]] == 1:
                cur -= 1
            d[c[cr]] -= 1
            cr -= 1
        while l > cl:
            if d[c[cl]] == 1:
                cur -= 1
            d[c[cl]] -= 1
            cl += 1
        ans[i] = cur
    prn(ans)
    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    m2 = m * m
    g = [0]*q
    for i in range(q):
        l, r = nm()
        g[i] = ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    b = BIT(m)
    last = [n + 5]*(n+1)
    cr = -1
    for r in g:
        i = r & mask
        r >>= 20
        l = r & mask
        r >>= 20
        while cr < r:
            cr += 1
            b.bitadd(last[c[cr]], -1)
            last[c[cr]] = cr
            b.bitadd(cr, 1)
        ans[i] = b.bitsum(l, r+1)
    prn(ans)
    return

solve()