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

from collections import Counter

H, W, M = [int(n) for n in input().split()]
h = []
w = []
for m in range(M):
    tmp = [int(n) for n in input().split()]
    h.append(tmp[0])
    w.append(tmp[1])

h_counter = Counter(h)
w_counter = Counter(w)

most_common_h_list = []
most_common_w_list = []

most_common_h_count = 0
for k, v in h_counter.most_common():
    if v < most_common_h_count:
        break
    most_common_h_list.append(k)
    most_common_h_count = v

most_common_w_count = 0
for k, v in w_counter.most_common():
    if v < most_common_w_count:
        break
    most_common_w_list.append(k)
    most_common_w_count = v

ans = []
for hh in most_common_h_list:
    for ww in most_common_w_list:
        for m in range(M):
            if h[m] == hh and w[m] == ww:
                ans.append(most_common_h_count + most_common_w_count - 1)
                break
        else:
            ans.append(most_common_h_count + most_common_w_count)

ans = sorted(ans, reverse=True)
print(ans[0])


### FIXED CODE ###

H, W, M = [int(n) for n in input().split()]
H_freq = [0] * H
W_freq = [0] * W

table = []
for m in range(M):
    h, w = [int(n)-1 for n in input().split()]
    H_freq[h] += 1
    W_freq[w] += 1
    table.append((h, w))

max_h = max(H_freq)
max_w = max(W_freq)
most_freqent_h = [i for i, h in enumerate(H_freq) if h == max_h]
most_freqent_w = [i for i, w in enumerate(W_freq) if w == max_w]

count = 0
for (h, w) in table:
    if H_freq[h] == max_h and W_freq[w] == max_w:
        count += 1

if count < len(most_freqent_h) * len(most_freqent_w):
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)
### BUGGY CODE ###

n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
if ans < 0:
    ans += mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
if ans < 0:
    ans += mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

from statistics import median
from itertools import combinations

N = int(input())
num_lis = [int(_) for _ in input().split()]

for i in range(N):
    tmp = num_lis.copy()
    del tmp[i]
    print(median(tmp))

### FIXED CODE ###


N = int(input())
X = [int(_) for _ in input().split()]
tmp = sorted(X)

one = N // 2 - 1
two = N // 2

for x in X:
    if x <= tmp[one]:
        print(tmp[two])
    else:
        print(tmp[one])
### BUGGY CODE ###

import numpy as np
import bisect
INF = 10 ** 9 + 7
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aset = set(a)
bset = set(b)
ablst = [0] * ((N * M) + 1)
a.sort(), b.sort()

if len(aset) != len(a) or len(bset) != len(b):
    print(0)
    exit()

na = np.array(a)
nb = np.array(b)
for i in range(N):
    ablst[na[i]] += 1

for j in range(M):
    ablst[nb[j]] += 1
ans = 1
for i in range(N * M, 0, -1):
    ac = bisect.bisect_left(na, i)
    bc = bisect.bisect_left(nb, i)
    if ablst[i] == 2:
        ans *= 1
    elif ablst[i] == 1 and ac < N and na[ac] == i:
        ans *= (M - bc)
    elif ablst[i] == 1 and bc < M and nb[bc] == i:
        ans *= (N - ac)
    else:
        ans *= (N - ac) * (M - bc) - (N * M - i)
    ans %= INF
print(ans % INF)


### FIXED CODE ###

import bisect
INF = 10 ** 9 + 7
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aset = set(a)
bset = set(b)
ablst = [0] * ((N * M) + 1)
a.sort(), b.sort()

if len(aset) != len(a) or len(bset) != len(b):
    print(0)
    exit()

for i in range(N):
    ablst[a[i]] += 1

for j in range(M):
    ablst[b[j]] += 1

ans = 1
for i in range(N * M, 0, -1):
    ac = bisect.bisect_left(a, i)
    bc = bisect.bisect_left(b, i)
    if ablst[i] == 2:
        ans *= 1
    elif ablst[i] == 1 and ac < N and a[ac] == i:
        ans *= (M - bc)
    elif ablst[i] == 1 and bc < M and b[bc] == i:
        ans *= (N - ac)
    else:
        acnt = bisect.bisect_left(a, i)
        bcnt = bisect.bisect_left(b, i)
        ans *= (N - ac) * (M - bc) - (N * M - i)
    ans %= INF
print(ans % INF)
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline

H, W = map(int, input().split())
q = []
a = [None] * H
for y in range(H):
    l = list(input())
    a[y] = l
    for x in range(W):
        if l[x] == '#':
            q.append((y,x))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1][qq[1]] == '.':
                a[qq[0] - 1][qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (H-1):
            if a[qq[0]+1][qq[1]] == '.':
                a[qq[0] + 1][qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0]][qq[1]-1] == '.':
                a[qq[0]][qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (W-1):
            if a[qq[0]][qq[1]+1] == '.':
                a[qq[0]][ qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)


### FIXED CODE ###

h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '#'
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

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

import sys

n = int(raw_input())
print 0
status_0 = raw_input()
check = n / 2
if check % 2 == 1:
    check += 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            check += check / 2
        else:
            check -= check / 2

sys.stdout.flush()


### FIXED CODE ###

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

import sys

n = int(raw_input())
print 0
sys.stdout.flush()
status_0 = raw_input()
start = 0
end = n-1
check = end
i = 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        sys.stdout.flush()
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            if check % 2 == 0:
                start = check
            else:
                end = check
        else:
            if check % 2 == 0:
                end = check
            else:
                start = check
        check = start+(end-start)/2

quit()
### BUGGY CODE ###


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

xy_list = []
for i in range(N):
    xy_list.append(list(map(int,input().split())))
min_s = 10**28    
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                max_x = max(xy_list[i][0],xy_list[j][0])
                min_x = min(xy_list[i][0],xy_list[j][0])
                max_y = max(xy_list[k][1],xy_list[l][1])
                min_y = min(xy_list[k][1],xy_list[l][1])
                count = 0
                for m in range(N):
                    if max_x>=xy_list[m][0] and min_x<=xy_list[m][0] and max_y>=xy_list[m][1] and min_y<=xy_list[m][1]:
                        count+=1
                if count==K:
                    min_s = min((max_x-min_x)*(max_y-min_y),min_s)

print(min_s)

### FIXED CODE ###

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

X = []
Y = []
Z = []
for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    Z.append([x,y])

X.sort()
Y.sort()

min_rec=10**27

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for l in range(k+1,N):
                count=0
                for n in range(N):
                    if Z[n][0]>=X[i] and Z[n][0]<=X[j] and Z[n][1]>=Y[k] and Z[n][1]<=Y[l]:
                        count+=1
                if count==K:
                    min_rec = min(min_rec,(X[j]-X[i])*(Y[l]-Y[k]))

print(min_rec)
### BUGGY CODE ###

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


total=0

for i in range(n-1):
    total+=a[i]%mod * (sum(a[i+1:]))%mod
    total%=mod

print(total)


### FIXED CODE ###

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

A=sum(a)%mod
total=0

for i in range(n-1):
    A-=a[i]
    total+=A*a[i]
    total%=mod

print(total)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_list.insert(0,0)
sum = 0
for i in range(1, N):
    for j in range(i + 1, N + 1):
        sum += (A_list[i] * A_list[j]) 
        sum = sum % 1000000007
print(sum)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)

cum_sum = 0
cum_sum_list = []
for i in range(N + 1):
    cum_sum += A_list[i]
    cum_sum_list.append(cum_sum)

ans = 0
for i in range(1, N+1):
    ans += A_list[i] * (cum_sum_list[N] - cum_sum_list[i])
    ans = ans % 1000000007
print(ans)
### BUGGY CODE ###

from fractions import gcd
K = int(input())
ans = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        n = gcd(i,j)
        for k in range(1,K+1):
            ans += gcd(k,n)

print(ans)



### FIXED CODE ###

from fractions import gcd
K = int(input())
ans = 0
dp = [0]*201

for i in range(1,K+1):
    for j in range(1,K+1):
        S = 0
        n = gcd(i,j)
        if dp[n] != 0:
            ans += dp[n]
        else:
            for k in range(1,K+1):
                S += gcd(k,n)
            ans += S
            dp[n] = S

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

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_flag = []
    for i in range(N-1):
        if S[i:i+2] == 'AC':
            ac_flag.append(1)
        else:
            ac_flag.append(0)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(sum(ac_flag[l-1:r-1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_freq = [0]
    for i in range(0, N-1):
        if S[i:i+2] == 'AC':
            ac_freq.append(ac_freq[-1] + 1)
        else:
            ac_freq.append(ac_freq[-1])
    ac_freq.append(ac_freq[-1])
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ac_freq[r-1] - ac_freq[l-1])


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

def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]
 
for i in m:
    if canProd(0,i):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r + 1) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])
### BUGGY CODE ###

lis=list(map(int,input().split()))
alist=[]
for i in range(lis[1]):
    alist.append(int(input()))
steps=[0]*(lis[0]+2)
steps[1]=1
for i in range(2,lis[0]+2):
    if i-1 not in alist:
        steps[i]=(steps[i-1]+steps[i-2])%((10**9)+7)
ans=steps[-1]
print(ans)


### FIXED CODE ###

lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)
### BUGGY CODE ###

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

n = input()
class DoubleLinkedList(object):
    def __init__(self):
        self.next = None
        self.prev = None
        self.value = None
        
    def insert(self, value):
        new = DoubleLinkedList()
        new.next = self.next
        new.prev = self
        self.next.prev = new
        self.next = new
        new.value = value
        
    def delete(self):
        next = self.next
        prev = self.prev
        self.next.prev = prev
        self.prev.next = next

head = DoubleLinkedList()
tail = DoubleLinkedList()
head.next = tail
tail.prev = head

for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        head.insert(int(command[1]))
    elif command[0] == "delete":
        key = int(command[1])
        e = head.next
        while True:
            if e is tail:
                break
            if e.value == key:
                e.delete()
                break
            e = e.next
    elif command[0] == "deleteFirst":
        if not head.next is tail:
            head.next.delete()
    elif command[0] == "deleteLast":  
        if not tail.prev is head:
            tail.prev.delete()
    
e = head.next
while True:
    if e is tail:
        break
    print e.value,
    e = e.next

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = input()
l = []
tail = 0
for i in xrange(n):
    cmd = raw_input().split()
    if cmd[0] == "insert":
        l.append(cmd[1])
    elif cmd[0] == "delete":
        try:
            l.pop(len(l) - l[::-1].index(cmd[1]) -1)
        except ValueError:
            pass
    elif cmd[0] == "deleteFirst":
        l.pop()
    elif cmd[0] == "deleteLast":
        tail += 1

print " ".join(l[tail:][::-1])
### BUGGY CODE ###

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[[xs,ys,0],[xt,yt,0]]
xyr+=[list(map(int,input().split())) for _ in range(n)]
g=[[]for _ in range(n+2)]
for i in range(n+2):
  for j in range(n+2):
    if i==j:continue
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    g[i].append([d,j])
    g[j].append([d,i])
from heapq import heappop,heappush
todo=[[0,0]]
ka=set(())
seen=[-1]*(n+2)
seen[0]=0
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  if v==1:
    print(d)
    exit()
  ka.add(v)
  for nd,nv in g[v]:
    if seen[nv]==-1 or seen[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      seen[nv]=d+nd


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

lines = sys.stdin.readlines()

for i in range(0,m):

    l =  lines[i].split()
    p = int(l[0])
    y = int(l[1])
    py.append([p,y])     
    if p-1 in od :
        od[p-1].append(y)
    else:
        od[p-1] = [y]

#print(od)
for o in od.values() :
    o.sort()

for i in range(0,m):
    py0 = py[i][0] 
    r = od[py0-1].index(py[i][1])

    tmp = py0
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = tmp // 10
    
    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(py0,end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(r+1)

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
### BUGGY CODE ###

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

def checkIn(a, n):
    return (a[0] in a[1:n])

b = False
while(n > 1):
    if(checkIn(a,n)):
        print("NO")
        b = True
        break
    else:
        pass
    a = a[1:n]
    n = n-1

if(not b):
    print("YES")

### FIXED CODE ###

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

a.sort()
b = False
for i in range(n-1):
    if(a[i-1] == a[i]):
        print("NO")
        b = True
        break

if(not b):
    print("YES")
### BUGGY CODE ###

n = int(input())
a = [num for num in map(int, input().split())]

ans = 1

for i in range(n):
  ans = ans * a[i]
  
if ans > (10 ** 18):
  ans = -1

print(ans)

### FIXED CODE ###

import sys

n = int(input())
a = [num for num in map(int, input().split())]

if min(a) == 0:
  print(0)
  sys.exit(0)

ans = 1
m = 10 ** 18

for i in range(n):
  ans = ans * a[i]
  
  if ans > m:
    ans = -1
    break

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

from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for l, r, k in m:
        if right != r:
            for i in range(right, r):
                if pos[c[i]]:
                    tree.update(pos[c[i]], 0)
                pos[c[i]] = i+1
                tree.update(i+1, 1)
        ans[k] = tree.get(l, r+1)
        right = r

    for i in ans:
        print(i)


solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

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

a = []
for i in range(m):
    l,r = map(int,input().split())
    
    if i == 0:
        for j in range(l,r+1):
            a.append(j)
    else:        
        b = []
        for j in range(l,r+1):
            b.append(j)

        c = a.copy()
        for j in c:
            if not j in b:
                a.remove(j)
       
print(len(a))

### FIXED CODE ###

n,m = map(int,input().split())
 
min,max  = map(int,input().split())
for i in range(m-1):
    l,r = map(int,input().split())

    if l > max:
        print(0)
        exit(0)

    if r < min:
        print(0)
        exit(0)
 
    if l > min:
        min = l
    
    if r < max:
        max = r
  
 
print(max-min+1)