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

def solve():
    from bisect import bisect_left

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    M = max(A) + max(B)
    K = len(bin(M)) - 2
    mask = (1 << K) - 1
    k = K - 1
    T = 1 << k
    ans = 0
    while k >= 0:
        for i in range(N):
            B[i] &= mask
            A[i] &= mask
        B.sort()
        A.sort(reverse=True)
        bit = 0
        T1, T2, T3, T4 = 0, 0, 0, 0
        for a in A:
            T1 = bisect_left(B, T - a, T1)
            T2 = bisect_left(B, 2 * T - a, T2)
            T3 = bisect_left(B, 3 * T - a, T3)
            T4 = bisect_left(B, 4 * T - a, T4)
            bit += (T4 - T3) + (T2 - T1)
            bit &= 1
        ans += bit * T
        k -= 1
        T >>= 1
        mask >>= 1

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    # from bisect import bisect_left
    import sys

    N = int(input())
    A = [int(x) for x in sys.stdin.readline().split()]
    B = [int(x) for x in sys.stdin.readline().split()]
    M = max(A) + max(B)
    K = len(bin(M)) - 2
    mask = (1 << K) - 1
    k = K - 1
    T = 1 << k
    ans = 0
    while k >= 0:
        for i in range(N):
            B[i] &= mask
            A[i] &= mask
        B = list(sorted(b & mask for b in B))
        A = list(sorted(a & mask for a in A))
        bit = 0
        T1, T2, T3 = 0, 0, 0
        for a in reversed(A):
            while T1 < N and a + B[T1] < T:
                T1 += 1
            while T2 < N and a + B[T2] < 2 * T:
                T2 += 1
            while T3 < N and a + B[T3] < 3 * T:
                T3 += 1
            # T1 = bisect_left(B, T - a, T1)
            # T2 = bisect_left(B, 2 * T - a, T2)
            # T3 = bisect_left(B, 3 * T - a, T3)
            # T4 = bisect_left(B, 4 * T - a, T4)
            bit += (N - T3) + (T2 - T1)
            bit &= 1
        ans += bit * T
        k -= 1
        T >>= 1
        mask >>= 1

    print(ans)


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

N = int(input())
l = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += (l[i] * l[j])
print(ans%mod)

### FIXED CODE ###

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

area = sum(l) * sum(l)

for i in l:
    area -= i*i

ans = area//2
ans = ans % mod
print(ans)
### BUGGY CODE ###

import sys
from collections import deque


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

s = input()
q = inint()

S = deque()

for i in range(len(s)):
    S.append(s[i])

for i in range(q):
    Q = instrl()
    if Q[0] == "1":
        S.reverse()
    else:
        if Q[1] == "1":
            S.appendleft(Q[2])
        else:
            S.append(Q[2])

print("".join(S))

### FIXED CODE ###

import sys
from collections import deque


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

s = input()
q = inint()

S = deque()
f = [0,1]

for i in range(len(s)):
    S.append(s[i])

for i in range(q):
    Q = instrl()
    if Q[0] == "1":
        f = f[::-1]
    else:
        if f[0] == 0:
            if Q[1] == "1":
                S.appendleft(Q[2])
            else:
                S.append(Q[2])
        else:
            if Q[1] == "1":
                S.append(Q[2])
            else:
                S.appendleft(Q[2])

if f[0] == 1:
    S.reverse()

print("".join(S))
### BUGGY CODE ###

import sys

n, q = map(int, input().split())
sys.setrecursionlimit(2 * (10 ** 5))

adj_list = [[] for _ in range(n + 1)]

for i in range(n - 1):
    u, v = map(int, input().split())
    adj_list[u].append(v)
    adj_list[v].append(u)

val = [0] * (n + 1)
visited = [False] * (n + 1)

for i in range(q):
    p, x = map(int, input().split())
    val[p] += x


def dfs(val, adj_list, visited, cur, prev):
    if prev != -1:
        val[cur] += val[prev]

    visited[cur] = True

    for next in adj_list[cur]:
        if visited[next] is False:
            dfs(val, adj_list, visited, next, cur)


dfs(val, adj_list, visited, 1, -1)

for i in range(n):
    print(val[i + 1], end="")
    if i != n - 1:
        print(" ", end="")
    else:
        print()



### FIXED CODE ###

from collections import deque

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

adj_list = [[] for _ in range(n + 1)]
val = [0] * (n + 1)
visited = [False] * (n + 1)

for i in range(n - 1):
    u, v = map(int, input().split())
    adj_list[u].append(v)
    adj_list[v].append(u)

for i in range(q):
    p, x = map(int, input().split())
    val[p] += x

dq = deque()
prev = -1
cur = 1
dq.append([cur, prev])

while len(dq) > 0:

    cur, prev = dq.popleft()
    if prev != -1:
        val[cur] += val[prev]
    visited[cur] = True

    for next in adj_list[cur]:
        if visited[next] is False:
            dq.append([next, cur])

print(*val[1:])
### BUGGY CODE ###

import sys
from io import StringIO
import unittest
import math

def resolve():
    x = int(input())

    a = math.floor(x ** 0.2)

    b5 = a ** 5 - x
    b = 0

    if b5 != 0:
        while 1:
            b -= 1
            if b5 == (b ** 5):
                break

    print(a, b, sep=' ')


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """33"""
        output = """2 -1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1"""
        output = """0 -1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest
import math

def resolve():
    x = int(input())

    a = math.floor(x ** 0.2) + 1

    b5 = a ** 5 - x

    if x == 1:
        a = 0
        b = -1
    elif b5 == 0:
        b = 0
    else:
        right = (10 ** 9)
        left = -1 * (10 ** 9)
        pre_right = (10 ** 9)
        pre_left = -1 * (10 ** 9)

        b = 0
        pre_mid = 10 ** 9
        while 1:
            mid = (right + left) // 2
            ans = mid ** 5
            # print(left, right)

            if ans > b5:
                right = mid - 1
            elif ans < b5:
                left = mid + 1
            else:
                b = mid
                break

            if [pre_right, pre_left] == [right, left]:
                a -= 1
                b5 = a ** 5 - x
                right = (10 ** 9)
                left = -1 * (10 ** 9)

            pre_right = right
            pre_left = left

    print(a, b, sep=' ')


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """33"""
        output = """2 -1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1"""
        output = """0 -1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()
### BUGGY CODE ###

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

def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    for i in range(1,n+1):
        print(l.count(i))
resolve()

### FIXED CODE ###

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

def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    ll=[0]*n
    for i in range(n-1):
        ll[l[i]-1]+=1
    for i in ll:
        print(i)
resolve()
### BUGGY CODE ###

n = int(input())
ans = 1
A = list(map(int,input().split()))
for x in A:
  if x == 0:
    print(0)
    exit(0)
  ans *= x
if ans > 10**18:
  print(-1)
  exit(0)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit(0)
for x in A:
  ans *= x
  if ans > 10**18:
    print(-1)
    exit(0)
print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    d = {}
    d2 = {}
    d[0] = [0]
    s = 0
    for i in range(1, N+1):
        s = s + A[i-1]
        t = (s-i) % K
        if t in d:
            d[t].append(i)
        else:
            d[t] = [i]
        d2[i] = t
    a = 0
    for i in range(1, N+1):
        for j in d[d2[i]]:
            if i - K < j and j < i:
                a += 1
    return a

print(main())


### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    A = list(map(int, input().split()))
    s = 0
    d = {}
    d[0] = {0}
    r = 0
    l = [0] * (N + 1)
    for i, v in enumerate(A, start=1):
        if i - K >= 0:
           x = l[i - K]
           d[x].remove(i-K)
        s += v % K
        s %= K
        t = (s - i) % K
        l[i] = t
        if t in d:
            r += len(d[t])
            d[t].add(i)
        else:
            d[t] = {i}
    return r
print(main())
### BUGGY CODE ###

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
time= 0

first = n
second = 0
third = 0
forth = 0
fifth = 0
goal = 0

while goal != n:
    time += 1


    #6
    if fifth < e:
        e_moved = fifth
    else:
        e_moved = e
    fifth = fifth - e_moved
    goal = goal + e_moved

    #5
    if forth < d:
        d_moved = forth
    else:
        d_moved = d
    forth = forth - d_moved
    fifth = fifth + d_moved

    #4
    if third < c:
        c_moved = third
    else:
        c_moved = c
    third = third - c_moved
    forth = forth + c_moved

    #3
    if second < b:
        b_moved = second
    else:
        b_moved = b
    second = second - b_moved
    third = third + b_moved

    #2
    if first < a:
        a_moved = first
    else:
        a_moved = a
    first = first - a_moved
    second = second + a_moved


print(time)


### FIXED CODE ###

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
time= 0

minroute = min([a,b,c,d,e])

time = (-(-n//minroute)) + 4

print(time)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)


count = 0
# i<n-1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(n-1, i, -1):
            if a[i] % a[j] == 0:
                break
            if j == i+1:
                count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
Max = a[-1]
memo = [1] * (Max+1)
count = 0

# i<n-1
for i in range(n-1):
    t = a[i]
    if memo[t] == 1:
        if a[i] != a[i+1]:
            count += 1
        for j in [t*k for k in range(1, Max//t+1)]:
            memo[j] = 0
# i=n-1
if memo[a[n-1]] == 1:
    count += 1

print(count)

""" #Time over
a.sort(reverse=True)

count = 0
# i<n-1
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(n-1, i, -1):
            if a[i] % a[j] == 0:
                break
            if j == i+1:
                count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)
"""
### BUGGY CODE ###

from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')

n,k=mp()
l=li()
dp=[INF for i in range(n)]
dp[0]=0

for i in range(n):

    for j in range(i+1,min(i+k+1,n)):

        dp[j]=min(abs(l[i]-l[j])+dp[i],dp[j])

print(dp[-1])

        


### FIXED CODE ###

from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')

n,k=mp()
l=li()
dp=[INF for i in range(n)]
dp[0]=0

for i in range(n):

    for j in range(i+1,min(i+k+1,n)):

        dp[j]=min(abs(l[i]-l[j])+dp[i],dp[j])

print(dp[-1])
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        numera = 4 * h * n - n * N - h * N
        denomi = h * n * N
        if numera <= 0:
            continue
        elif denomi % numera != 0:
            continue
        w = denomi // numera
        print(h, n, w)
        exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        numera = 4 * h * n - n * N - h * N
        denomi = h * n * N
        if numera <= 0:
            continue
        elif denomi % numera != 0:
            continue
        w = denomi // numera
        print(h, n, w)
        exit()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
pl=1
visit=[1]
loop=0
q=True
v=True
cnt=0
br=False
while q:
    cnt+=1
    pl=a[pl-1]
    for i in visit:
        if pl==i:
            loop=visit.index(pl)
            br=not br
            break
    if br:
        break
    visit.append(pl)
    if cnt==k:
        print(pl)
        v=not v
        break
    if cnt==10**7:
        q=not q
if v:
    loop_len=cnt-loop
    q=True
    k=(k-loop)%loop_len
    cnt=0
    if k==0:
        print(pl)
    else:
        while q:
            cnt+=1
            pl=a[pl-1]
            if cnt==k:
                print(pl)
                break
            if cnt==10**7:
                q=not q

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
pl=1
visit=[-1]*n
visit[0]=0
loop=0
q=True
v=True
cnt=0

while q:
    cnt+=1
    pl=a[pl-1]
    if visit[pl-1]!=-1:
        loop=visit[pl-1]
        break
    visit[pl-1]=cnt
    if cnt==k:
        print(pl)
        v=not v
        break
    if cnt==10**7:
        q=not q
if v:
    loop_len=cnt-loop
    q=True
    k=(k-loop)%loop_len
    cnt=0
    if k==0:
        print(pl)
    else:
        while q:
            cnt+=1
            pl=a[pl-1]
            if cnt==k:
                print(pl)
                break
            if cnt==10**7:
                q=not q
### BUGGY CODE ###

N,K = map(int,input().split())
ary = [0]+list(map(int,input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]
ary = sorted(ary)
a = ary.index(0)
ans = float("Inf")
for i in range(N+1):
    for j in range(N+1):
        dp[i][j] = abs(ary[i]-ary[j])
for i in range(N+1):
        if i == a:continue
        k = abs(i - a)
        d = abs(ary[i])
        if k >= K and ans > d:
            ans = d
        if i <= a:
            k = K - abs(i-a)
            d = abs(ary[i])
            if k > 0:
                d += dp[i][a+k]
                if ans > d:
                    ans = d
print(0 if ans == float("Inf") else ans)

### FIXED CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary.sort()
zero = ary.index(0)
a = [abs(i - zero) for i in range(N + 1)]
ary.pop(zero)
ans = float("Inf")
for i in range(N - K + 1):
    b = N - i - 1
    d = abs(ary[i])
    if a[i] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[i] - ary[i + K - 1]))
    d = abs(ary[b])
    if a[b] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[b] - ary[b - K + 1]))
print(ans)
### BUGGY CODE ###

def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    Q = []
    for i in range(n)[::-1]:
        Q.append(-1)
        Q.append(i)
        Q.append(3)
        Q.append(i)
        Q.append(2)
        Q.append(i)
        Q.append(1)
    while Q:
        tp = Q.pop()
        if tp == 2:
            j = Q.pop()
            if done[j]: continue
            done[j] = 1
            L.append(j)
            checking[j] = 0
            continue
        elif tp == 3:
            j = Q.pop()
            k = Q.pop()
            D[j] = max(D[j], (D[k] + 1 if k >= 0 else 0))
        elif tp == 1:
            j = Q.pop()
            if done[j]: continue
            checking[j] = 1
            for k in E[j]:
                if checking[k]:
                    return []
                Q.append(k)
                Q.append(j)
                Q.append(3)
                Q.append(k)
                Q.append(2)
                Q.append(k)
                Q.append(1)
    return L[::-1]
def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)


### FIXED CODE ###

N = int(input())
X = [[int(a)-1 for a in input().split()] for _ in range(N)]
Y = [0] * N
Z = [-1] * N

L = [a for a in range(N)]
f = 1
d = 0
c = 0
while f:
    d += 1
    f = 0
    NL = []
    for l in L:
        a, aa = Y[l], Z[l]
        if a >= N - 1: continue
        ll = X[l][a]
        b, bb = Y[ll], Z[ll]
        if b >= N - 1: continue
        lll = X[ll][b]
        if lll == l and aa < d and bb < d:
            f = 1
            c += 1
            Y[l] += 1
            Z[l] = d
            if Y[l] < N - 1: NL.append(l)
            Y[ll] += 1
            Z[ll] = d
            if Y[ll] < N - 1: NL.append(ll)
    if c == N*(N-1)//2:
        print(d)
        break
    L = NL
else:
    print(-1)
### BUGGY CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()
for i in t:
	for j in s:
		if int(i)==int(j):
			c +=1
			break
print(c)


### FIXED CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()

print(len(set(s)&set(t)))
### BUGGY CODE ###

from collections import deque
def main():
    n = int(input())
    b = list(map(int, input().split()))
    s = set()
    q = deque()

    q.append([tuple(b), [0]*n, 0])
    ans = None
    while q:
        now, history, depth = q.popleft()
        if now in s:
            continue
        s.add(now)
        if len(now) == 0:
            ans = history
            break
        for i, j in enumerate(now):
            if i+1 == j:
                tmp = history[::]
                tmp[depth] = i+1
                q.appendleft([tuple(now[:i] + now[i+1:]), tmp, depth+1])
    if ans is None:
        print(-1)
    else:
        for i in ans[::-1]:
            if i == 0:
                break
            print(i)
if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def check(b):
    for i in range(len(b))[::-1]:
        if i+1 == b[i]:
            return i
    return -1

ans = []
for i in range(n):
    ind = check(b)
    if ind >= 0:
        ans.append(ind+1)
        b = b[:ind] + b[ind+1:]
    else:
        print(-1)
        exit()
for i in ans[::-1]:
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3

def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a%b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m+x%m) % m


def mod_comb(n, k, mod):
    mul, div = 1, 1
    for i in range(k):
        mul *= (n-i)
        div *= (i+1)
        mul %= mod
        div %= mod
    return mul * mod_inverse(div, mod) % mod


n, k = map(int, input().split())
a = [ int(x) for x in input().split() ]
a.sort(reverse=True)

mod = int(1e9)+7
ans = 0

for i, v in enumerate(a):
    ans += v*mod_comb(n-i-1, k-1, mod)
    ans %= mod
    ans -= v*mod_comb(i, k-1, mod)
    ans %= mod
    
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

MOD = int(1e9)+7

def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a%b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m+x%m) % m


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

maxf = 2*n + 10
f = [1 for _ in range(maxf)]
invf = [1 for _ in range(maxf)]

for i in range(1, maxf):
    f[i] = (i * f[i - 1]) % MOD
 
invf[maxf-1] = pow(f[maxf - 1], MOD-2, MOD)
for i in range(maxf-1, 0, -1):
    invf[i-1] = (i*invf[i]) % MOD
 
def comb(a, b):
    if b > a:
        return 0
    return (((f[a]*invf[b]) % MOD) * invf[a-b]) % MOD

a = [ int(x) for x in input().split() ]
a.sort(reverse=True)

ans = 0

for i, v in enumerate(a):
    ans += v*comb(n-i-1, k-1)
    ans %= MOD
    ans -= v*comb(i, k-1)
    ans %= MOD
    
print(ans)
### BUGGY CODE ###

from collections import deque
A =input()
S = deque(A)
H = 0
Q = int(input())
Qlist = []
for i in range(Q):
    Qlist.append(list((map(str,input().split()))))
for i in range(Q):
    op = Qlist[i]
    if len(op) ==1:
        H +=1
    else:
        if op[1] =='1':
            if H%2 == 0:
                S.appendleft(op[2])
            else:
                S.append(op[2]) 
        else:
            if H%2 == 0:
                S.append(op[2])
            else:
                S.appendleft(op[2])
if H%2 == 1:
    A = S[-1]
    for i in range(1,len(S)):
        A += S[-i-1]
else:
    A = S[0]
    for i in range(1,len(S)):
        A += S[i]
print(A)

### FIXED CODE ###

from collections import deque
S= deque(input())
Q = int(input())
ba = 1
for i in range(Q):
    Query =list(map(str,input().split()))
    Query0 = Query[0]
    if Query[0] == '1':
        ba *= -1
    else:
        if Query[1] == '1' and ba ==1:
            S.appendleft(Query[2])
        elif Query[1] == '1' and ba ==-1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==-1:
            S.appendleft(Query[2])
if ba == -1:
    S.reverse()
mojieru = ''.join(S)
print(mojieru)
### BUGGY CODE ###

from numpy import*
from numba import*
@njit('i8[:](i8,i8,i8[:],i8[:,:])',cache=True)
def main(n,q,c,z):
  a=zeros(q,int64)
  t=zeros(9**6,int64)
  b=zeros(9**6,int64)
  j=0
  for i in argsort(z[:,1]):
    l,r=z[i,0],z[i,1]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:
        t[x]+=1
        x+=x&-x
      while y<=n:
        t[y]-=1
        y+=y&-y
    while l:
      a[i]+=t[l]
      l-=l&-l
  return a
(n,q),c,*z=[int_(t.split())for t in open(0)]
print(' '.join(map(str,main(n,q,c,int_(z)).tolist())))

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()