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

s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1

        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0 and j > 0:
  if s[i-1]==t[j-1]:
    ans=s[i-1]+ans
    i=i-1
    j=j-1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
print(ans)


### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1

        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0 and j > 0:
  if s[i-1]==t[j-1]:
    ans=s[i-1]+ans
    i=i-1
    j=j-1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  import bisect

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

  A_m = [abs(int(x)) for x in A if x < 0]
  A_m.sort()
  N_m = len(A_m)

  A_p = [int(x) for x in A if x > 0]
  A_p.sort()
  N_p = len(A_p)

  M = N_m * N_p
  P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
  Z = (1 / 2) * N * (N - 1) - (M + P)

  if M < K <= M + Z:
      print(0)
      sys.exit()

  def cnt_M(x):
      cnt = 0
      for i in A_m:
          cnt += bisect.bisect_right(A_p, x // i)
      return cnt >= (M - K + 1)

  if K <= M:
      left = -1 - 10**18
      right = 1 + 10**18 
      while right - left > 1:
          mid = (left + right) // 2
          if cnt_M(mid):
              right = mid
          else:
              left = mid
      print(-right)
      sys.exit()
  K -= (M + Z)
  def cnt_P(x):
      cnt = 0
      ng = 0
      for i in A_m:
          cnt += bisect.bisect_right(A_m, x // i)
          if i ** 2 <= x:
              ng += 1
      for j in A_p:
          cnt += bisect.bisect_right(A_p, x // j)
          if j ** 2 <= x:
              ng += 1
      return (cnt - ng) // 2 >= K

  left = -1 - 10**18
  right = 1 + 10**18
  while right - left > 1:
      mid = (left + right) // 2
      if cnt_P(mid):
         right = mid
      else:
          left = mid

  print(right)
main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

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

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x // A_p, side="right").sum()
    return cnt >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while right - left> 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
 
    print(-right)
    sys.exit()

K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x // A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x // A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    cnt = (cnt - ng) // 2
    return cnt >= K

left = -1 - 10 ** 18
right = 1 + 10 ** 18

while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

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


def greatest_common_divisor(x, y):
    x_divisor = {i for i in range(1, x+1) if x % i == 0}
    y_divisor = {i for i in range(1, y+1) if y % i == 0}
    common_divisor = list(x_divisor.intersection(y_divisor))
    common_divisor.sort()
    print(common_divisor.pop(-1))


def to_xy(v):
    return [int(c) for c in v.split()]


if __name__ == '__main__':
    x, y = to_xy(input())
    greatest_common_divisor(x, y)

### FIXED CODE ###

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


def gcd(x, y):
    # GCD(Greatest Common Divisor)
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    print(x)


def to_xy(v):
    return [int(c) for c in v.split()]


if __name__ == '__main__':
    x, y = to_xy(input())
    gcd(x, y)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    counter = 0
    for item in A:
        if item == i:
            counter += 1
    print(counter)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count_list = [0] * N
for item in A:
    count_list[item-1] += 1
for countitem in count_list:
    print(countitem)
### BUGGY CODE ###

n=int(input())
a_=list(map(int,input().split()))
from collections import defaultdict
a=[[i,ai] for i,ai in enumerate(a_)]
sa=defaultdict(lambda:0)
# sa[(i,j)]:i番目の人までで自分の番号-身長がjの人
d=defaultdict(lambda:0)
# 自分の番号-身長の累計
mt=0
for i,ai in a:
  d[i-ai]+=1
  for k,v in d.items():
    sa[(i+1,k)]=v
ans=0
for i,ai in a:
  c=sa[(n,i+ai)]-sa[(i+1,i+ai)]
  ans+=c
print(ans)


### FIXED CODE ###

def main(n,a_):
  from collections import defaultdict
  lr=[[i+ai,i-ai] for i,ai in enumerate(a_)]
  rs=defaultdict(lambda:0)
  ls=defaultdict(lambda:0)
  ans=0
  for l,r in lr:
    rs[r]+=1
    ls[l]+=1
  for k in rs.keys():
    ans+=rs[k]*ls[k]
  print(ans)
if __name__=='__main__':
  n=int(input())
  a_=list(map(int,input().split()))
  #n=200000
  #a_=[3 for _ in range(n)]
  main(n,a_)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

ans = [None]*N
for i in range(1, N+1):
        ans[i-1] = A.index(i) + 1
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

ans = [None]*N
for i, order in enumerate(A, 1):
        ans[order-1] = i
print(" ".join(map(str, ans)))
### BUGGY CODE ###

S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * (N*2) for i in range(N)]
dp_y = [[False] * (N*2) for i in range(N)]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(N):
            if xi + X_command[i] >= N:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(N):
            if yi + Y_command[i] >= N:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

nx = X_command.pop(-1)
ny = 0

for xi in X_command:
    if nx > x:
        nx -= xi
    else:
        nx += xi

for yi in Y_command:
    if ny > y:
        ny -= yi
    else:
        ny += yi

if nx == x and ny == y:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

mod = 10 ** 9 + 7
s = input()[::-1]
l = len(s)
dp =[[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] =1
for i in range(l):
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * (10 ** i) + k) % 13] +=dp[i][k] % mod
    else:
        for k in range(13):
            dp[i + 1][(int(s[i]) * (10 ** i) + k) % 13] +=dp[i][k] % mod
print(dp[-1][5] % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0]=1
for i in range(n):
    if s[i] == '?': 
        for j in range(10):
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13]+=dp[i][k] % mod
    else:
        for k in range(13): 
            dp[i + 1][(k * 10+ int(s[i])) % 13]+=dp[i][k] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s)

list = []

for i in range(len(c)):
    if c.most_common()[i][1] == c.most_common()[0][1]:
        list.append(c.most_common()[i][0])
    else:
        break

list.sort()
for i in list:
    print(i)


### FIXED CODE ###

n = int(input())

d = {}
for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

list = []
maxnum = max(d.values())

for i in d:
    if d[i] == maxnum:
        list.append(i)
list.sort()
for i in list:
    print(i)
### BUGGY CODE ###

k, s = map(int, input().split())

cnt = 0
for i in range(k + 1):
  for j in range(k + 1):
    for l in range(k + 1):
      if i + j + l == s:
        cnt += 1

print(cnt)


### FIXED CODE ###

k, s = map(int, input().split())

cnt = 0
for i in range(k + 1):
  for j in range(k + 1):
      if 0 <= s - (i + j) <= k:
        cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = set([])
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    d %= 2
    done |= set([q])
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

### FIXED CODE ###

n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = [-1]*n
b[0] = 0
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b[q-1] = 0
    else:
        b[q-1] = 1
    for new_q in g[q]:
        v_,d_ = new_q
        if b[v_-1]==-1:
            queue.appendleft([v_,d+d_])
for i in b:
    print(i)
### BUGGY CODE ###

S = input()

# 下からi桁(1-indexed)まで使ったときの、13で割ったときあまりがjになるパターン
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    r_now = [1, 10, 9, 12, 3, 4][i%6]
    if s == "?":
        for d in range(10):
            for r_before, count in enumerate(dp[i]):
                j = (r_now*d+r_before)%13
                dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    else:
        d = int(s)
        for r_before, count in enumerate(dp[i]):
            j = (r_now*d+r_before)%13
            dp[i+1][j] += (dp[i+1][j]+count)%(10**9+7)
    # for dp_i in dp:
    #     print(dp_i)
    # print("")

print(dp[len(S)][5])

### FIXED CODE ###

S = input()

# 下からi桁(1-indexed)まで使ったときの、13で割ったときあまりがjになるパターン
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    r_now = [1, 10, 9, 12, 3, 4][i%6]
    if s == "?":
        for d in range(10):
            for r_before, count in enumerate(dp[i]):
                j = (r_now*d+r_before)%13
                dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    else:
        d = int(s)
        for r_before, count in enumerate(dp[i]):
            j = (r_now*d+r_before)%13
            dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    # for dp_i in dp:
    #     print(dp_i)
    # print("")

print(dp[len(S)][5])
### BUGGY CODE ###

N = int(input())
ans = sum(range(N))
print(ans)

### FIXED CODE ###

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

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
count = {}
c = 0
for i in range(n):
    s = input()
    count[s] = count.get(s,0)+1
ans = sorted([kv[0] for kv in count.items() if kv[1] == max(count.values())])
for item in ans:
    print(item)

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
count = {}
cmax = 0
for i in range(n):
    s = input()
    c = count.get(s,0)+1
    cmax = max(c,cmax)
    count[s] = c
ans = sorted([kv[0] for kv in count.items() if kv[1] == cmax])
for item in ans:
    print(item)
### BUGGY CODE ###

from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))

def divisors(n):
    i = 1
    result = set()
    while i * i <= n:
        if n % i == 0:
            result.add(i)
            result.add(n // i)
        i += 1
    return result

def solve(n, a):
    counts = {}
    for item in a:
        if item not in counts:
            counts[item] = 0
        counts[item] += 1
    items_in_a = set(a)
    result = 0
    for item in a:
        d = divisors(item)
        if len(items_in_a.intersection(d)) == 1 and counts[item] == 1:
            result += 1
    return result


if __name__ == "__main__":
    n = int_in()
    a = arr_in()
    out(solve(n, a))

### FIXED CODE ###

from math import sqrt
from sys import stdin, stdout
out = lambda o: stdout.write("{}\n".format(o))


def solve(a):
    a.sort()
    size = a[-1] + 1

    seive = [1] * size

    seen = set()
    for item in a:
        if item in seen:
            seive[item] = 0
        seen.add(item)

    for item in a:
        for j in range(2 * item, size, item):
            seive[j] = 0

    return sum(map(lambda x: seive[x], a))


if __name__ == "__main__":
    n = int(stdin.buffer.readline())
    a = [int(x) for x in stdin.buffer.readline().split()]
    out(solve(a))
### BUGGY CODE ###

import queue
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=queue.Queue()
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.put(i)
        while(not(q.empty())):
            r=q.get()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.put(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))




### FIXED CODE ###

N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())
l = []
for i in range(q):
  qy = input().split()
  l.append(qy)
  
st = s
count = 0
for i in range(q):
  k = l[i][0]
  if(k == '1'):
    count = (count + 1) % 2
  else:
    c = count
    d = int(l[i][1]) 
    e = l[i][2]
    if(c + d == 1 or c + d == 3):
      st = e + st
    elif(c + d == 2):
      st = st + e

if(count % 2 == 1):
  st = st[::-1]
      
print(st)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
sth = s
sth2 = ""
stm = ""
stm2 = ""
count = 0
flagh = 0
flagm = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count - 2
    d = int(k[1]) 
    e = k[2]
    if(c + d != 0):
      sth = e + sth
      if(len(sth) > 5000 and flagh == 0):
        flagh = 1
        sth2 = sth
        sth = ""
    else:
      stm = stm + e
      if(len(stm) > 5000 and flagm == 0):
        flagm = 1
        stm2 = stm
        stm = ""
      

st = sth + sth2 + stm2 + stm
if(count == 1):
  st = st[::-1]
  
print(st)
### BUGGY CODE ###


h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))

blackli = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            blackli.append((i, j))

bp = len(blackli)
dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
tmpblackli = []
allblackli = []
while bp != h * w:
    for li in blackli:
        for dx, dy in dd:
            nx = li[1] + dx; ny = li[0] + dy
            if 0 <= nx < w and 0 <= ny < h:
                tmpblackli.append((ny, nx))
    allblackli += blackli + tmpblackli
    allblackli = list(set(allblackli))
    blackli = []
    blackli += tmpblackli
    blackli = list(set(blackli))
    ans += 1
    bp = len(allblackli)
    tmpblackli = []
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
dist = [[-1]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            dist[i][j] = 0
            que.append((i, j))


dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
while que:
    y, x = que.popleft() #幅優先探索
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and dist[ny][nx] == -1:
            dist[ny][nx] = 0
            que.append((ny, nx))
            dist[ny][nx] = d + 1
print(d)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
ans = [A[i]+B[j]+C[k] for i in range(X) for j in range(Y) for k in range(Z) if (i+1)*(j+1)*(k+1) <= K]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
t =[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k) <= K:
                t.append(A[i]+B[j]+C[k])
            else:break
t.sort(reverse=True)
for i in range(K):
    print(t[i])
### BUGGY CODE ###

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N,Q=map(int,input().split())
*C,=map(set,input().split())
seg = SegTree(N,set.union,set())
seg.build(C)
for i in range(Q):
  l,r = map(int,input().split())
  print(len(seg.fold(l-1,r)))

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

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

sum = 0
for i in range(len(P)):
    for j in range(i+1):
        if P[i] > P[j]:
            sum += 1
            break

print(len(P)-sum)


### FIXED CODE ###

import itertools
N = int(input())
P = list(map(int, input().split()))

ac = list(itertools.accumulate(P, min))
ok = [P[i] <= ac[i] for i in range(len(P))]
print(ok.count(True))
### BUGGY CODE ###

p=10**9+7
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
x=[0 for i in range(N+1)]
x[0]=1
if 1 in a:
    x[1]=0
else:
    x[1]=x[0]
for i in range(2,N+1):
    x[i]=((x[i-1] if i-1 not in a else 0)+(x[i-2] if i-2 not in a else 0))%p

print(x[N])

### FIXED CODE ###

import bisect

p=10**9+7
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
x=[0 for i in range(N+1)]
x[0]=1
if 1 in a:
    x[1]=0
else:
    x[1]=x[0]
for i in range(2,N+1):
    if bisect.bisect_right(a,i-1)-bisect.bisect_left(a,i-1)==0: # i-1 not in a
        x[i]+=x[i-1]
    if bisect.bisect_right(a,i-2)-bisect.bisect_left(a,i-2)==0: # i-2 not in a
        x[i]+=x[i-2]
    x[i]%=p

print(x[N])