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

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            step = i+j
            if step < n:
                dp[step] = min(dp[step], dp[i]+abs(h[step]-h[i]))
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    stones = tuple(map(int, input().split()))
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


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

import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))
# from random import randint

# n = randint(1, 50)
# D = [randint(0, 12) for i in range(n)]

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(13):
    if C[i] >= 3:
        print(0)
        sys.exit()

D = []
for i in range(13):
    for j in range(C[i]):
        D.append(i)
n = len(D)
A = [0] * n
ans0 = 0
for i in range(2**n):
    ib = format(i, "b").zfill(n)
    for j in range(n):
        A[j] = D[j] * (-1) ** int(ib[j])
    ans = 30
    for j in range(n):
        for k in range(j+1, n):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
            if ans <= ans0:
                break
        if ans <= ans0:
            break
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))
# from random import randint

# n = randint(1, 50)
# D = [randint(0, 12) for i in range(n)]

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(13):
    if C[i] >= 3:
        print(0)
        sys.exit()

# D = []
# for i in range(13):
#     for j in range(C[i]):
#         D.append(i)
# n = len(D)
# A = [0] * n

# print(C)
ans0 = 0
for i in range(2**13):
    zero = 0
    ib = format(i, "b").zfill(13)
    A = []
    for j in range(13):
        if C[j] == 1:
            A.append(j * (-1) ** int(ib[j]))
        if C[j] == 2:
            if int(ib[j]) == 0:
                A.append(j)
                A.append(-j)
            else:
                zero = 1
    if zero == 1:
        continue
    # print("not cont")
    ans = 30
    # if len(A)>1:
        # print(A)
    # print(ib, A)
    for j in range(len(A)):
        for k in range(j+1, len(A)):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
            if ans <= ans0:
                break
        if ans <= ans0:
            break
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)
### BUGGY CODE ###

import sys
from operator import mul
from functools import reduce
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n = ni()
a = na()
a.sort()
l = a[-1]
ans = -1
for i in range(n):
    if l - a[i] - 1 > a[i]:
        continue
    else:
        if cmb(l, a[i]) > cmb(l, a[i - 1]):
            print(l, a[i])
        else:
            print(l, a[i-1])
        break



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
a.sort(reverse=True)
ans = -1
t = a[0]
target = (a[0] + (2 - 1)) // 2
#print(target)
pre = inf
if n == 2:
    print(max(a), min(a))
    sys.exit()
for i in range(1, n):
    #print(pre)
    dif = abs(target - a[i])
    if pre < dif:
        print(t, a[i-1])
        sys.exit()
    else:
        pre = dif
### BUGGY CODE ###

from sys import stdin

n, k = (int(x) for x in stdin.readline().rstrip().split())
p = [int(x) for x in stdin.readline().rstrip().split()]

m = 0
s = 0
total = 0
for i in range(n-k+1):
    a = sum([p[i+x] for x in range(k)])
    if m <= a:
        m = a
        s = i

for i in range(k):
    b = sum([x for x in range(1, p[s+i] + 1)])
    total += b/p[s+i]

print(total)


### FIXED CODE ###

from sys import stdin

n, k = (int(x) for x in stdin.readline().rstrip().split())
p = [int(x) for x in stdin.readline().rstrip().split()]
ev = [(i+1)/2 for i in p]
s = [ev[0]]
for i in range(1, n):
    s.append(s[i-1] + ev[i])

m = s[k-1]
for j in range(n-k):
    a = s[j+k] - s[j]
    if m < a:
        m = a

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

#!/usr/bin/env python3
import sys


def solve(K: int, S: int):
    cnt = 0
    for a in range(K + 1):
        for b in range(K + 1):
            for c in range(K + 1):
                if a + b + c == S:
                    cnt += 1
    print(cnt)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
 
 
def solve(K: int, S: int):
    cnt = 0
    for a in range(K + 1):
        for b in range(K + 1):
            tmp = S - (a + b)
            if 0 <= tmp and tmp <= K:
                cnt += 1 
    print(cnt)
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
commands = []
for a in range(n):
    raw = input().split()
    try:
        commands.append([raw[0], int(raw[1])])
    except:
        commands.append([raw[0], 'none'])

result = []
for a in commands:
    command, x = a[0], a[1]
    if command == 'insert':
        result.append(x)
    elif command == 'delete':
        if x in result:
            result.reverse()
            result.remove(x)
            result.reverse()
        else:
            continue
    elif command == 'deleteFirst':
        del result[-1]
    else:
        del result[0]

result.reverse()
print(*result)


### FIXED CODE ###

from collections import deque
import sys

n = int(input())
result = deque()
func = {'insert':result.appendleft,\
        'delete':result.remove,\
        'deleteFirst':result.popleft,\
        'deleteLast':result.pop}

for line in sys.stdin.readlines():
    c = line.split()
    if len(c) > 1:
        try:
            func[c[0]](int(c[1]))
        except:
            continue
    else:
        func[c[0]]()

print(*result)
### BUGGY CODE ###

from sys import exit

N, Q = map(int, input().split())

S = input()

AC = []
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        AC.append(i)

ans = []

for i in range(Q):
    li, ri = map(int, input().split())

    count = 0
    for ac in AC:
        if ac < li - 1:
            count += 1
        else:
            break
    for ac in reversed(AC):
        if ri - 1 < ac + 1:
            count += 1
        else:
            break
    ans.append(len(AC) - count)

for a in ans:
    print(a)


### FIXED CODE ###

from sys import exit

N, Q = map(int, input().split())

S = input()

AC = [0] * N

c = 0

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    AC[i + 1] = c

for _ in range(Q):
    li, ri = map(int, input().split())
    print(AC[ri - 1] - AC[li - 1])
### BUGGY CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = []

for i in range(0,n):
	kari = 0
	j = i
	while j<n-1 and h[j] >= h[j+1]:
		kari += 1
		j += 1
	ans.append(kari)

print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = 0

kari = 0
i = 0
for m in range(0,n-1):
	if h[m] >= h[m+1]:
		kari += 1
	else:
		kari = 0
	if ans < kari:
		ans = kari



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

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    R = [1]
    for i in range(n):
        R.append(R[-1] * A[i])

    prev = R[k]
    for i in range(k + 1, n + 1):
        now = R[i] // R[i - k]
        print("Yes" if prev < now else "No")
        prev = now


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(k, n):
        prev = A[i - k]
        now = A[i]
        print("Yes" if prev < now else "No")


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

in_li = list(map(int,input().split()))
A = in_li[0]
B = in_li[1]
K = in_li[2]
if A + B == K :
    print("0 0")
else :
    for i in range(K) :
        if A != 0 :
            A -= 1
        elif B != 0 :
            B -= 1
        else :
            pass
    print(A,"",B)


### FIXED CODE ###

in_li = list(map(int,input().split()))
A = in_li[0]
B = in_li[1]
K = in_li[2]
if A + B <= K :
    print("0 0")
else :
    if A > K :
        print(A-K,"",B)
    elif B > K - A :
        print("0",B-(K-A))
### BUGGY CODE ###

n = int(input())
s = input()
b = []
for i in range(n):
    if s[i] == '#':
        b.append(i)
if len(b) == 0:
    print(0)
else:
    ans = min(s[b[0]::].count('.'), s.count('#'))
    for i in range(1,len(b)-1):
        ans = min(ans, len(b[:i])+s[b[i]::].count('.'))
    print(ans)


### FIXED CODE ###

n = int(input())
s = input()
b = []
for i in range(n):
    if s[i] == '#':
        b.append(i)
if len(b) == 0:
    print(0)
else:
    ans = min(s[b[0]::].count('.'), s.count('#'))
    nb = len(b)
    for i in range(1,len(b)-1):
        ans = min(ans, i + n-b[i]-nb+i)
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	dp[0, 0] = a[0]
	dp[0, 1] = b[0]
	dp[0, 2] = c[0]
	for i in range(1, N):
		dp[i, 0] = max(dp[i-1, 1] + a[i], dp[i-1, 2] + a[i])
		dp[i, 1] = max(dp[i-1, 0] + b[i], dp[i-1, 2] + b[i])
		dp[i, 2] = max(dp[i-1, 0] + c[i], dp[i-1, 1] + c[i])
	print(max(dp[-1, :]))

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
# import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	activity = []
	for i in range(N):
		activity.append(LI())
	
	# dp = np.zeros((N, 3), dtype=int)
	dp = [[0, 0, 0] for _ in range(N)]
	dp[0][0] = activity[0][0]
	dp[0][1] = activity[0][1]
	dp[0][2] = activity[0][2]
	for i in range(1, N):
		dp[i][0] = max(dp[i-1][1] + activity[i][0], dp[i-1][2] + activity[i][0])
		dp[i][1] = max(dp[i-1][0] + activity[i][1], dp[i-1][2] + activity[i][1])
		dp[i][2] = max(dp[i-1][0] + activity[i][2], dp[i-1][1] + activity[i][2])
	print(max(dp[-1]))

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

from math import factorial
from bisect import bisect
n=int(input())
lst=sorted(map(int,input().split()))
ans_max=0
m=lst[-1]
index=bisect(lst,m/2)
if 0<=index-1:
    tmp=factorial(m)//factorial(m-lst[index-1])//factorial(lst[index-1])
    if tmp>ans_max:
        ans_max=tmp
        ans=[m,lst[index-1]]
if m!=lst[index]:
    tmp=factorial(m)//factorial(m-lst[index])//factorial(lst[index])
    if tmp>ans_max:
        ans_max=tmp
        ans=[m,lst[index]]
print(" ".join(map(str,ans)))

### FIXED CODE ###

from bisect import bisect
n=int(input())
lst=sorted(map(int,input().split()))
m=lst[-1]
index=bisect(lst,m/2)
if m!=lst[index]:
    q=lst[index]
    if 0<=index-1:
        p=lst[index-1]
        if abs(m/2-p)>=abs(m/2-q):
            print(m,q)
        else:
            print(m,p)
    else:
        print(m,q)
else:
    print(m,lst[index-1])
### BUGGY CODE ###

import statistics

N = int(input())

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

a = 0
while a < N:  
  B = [elem for idx,elem in enumerate(A) if idx != a]
  a += 1
  print(statistics.median(B))

### FIXED CODE ###

from sys import stdin
 
N = int(stdin.readline().rstrip())
 
A = [int(x) for x in stdin.readline().rstrip().split()]

B = sorted(A)
 
for i in range(N):  
  if A[i] < B[N//2]:
    print(B[N//2])
  else:
    print(B[N//2-1])
### BUGGY CODE ###

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = []
for i in range(N - 1):
  xa, a = X[i]
  xb, b = X[i + 1]
  edge.append((abs(xa - xb), (a, b)))
  ya, a = Y[i]
  yb, b = Y[i + 1]
  edge.append((abs(ya - yb), (a, b))) 
edge.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N + 1)
 
def find_root(x):
  y = root[x]
  if y == x:
    return x
  else:
    z = find_root(y)
    root[x] = z
    return z

def merge(x, y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return 0
  if comp_size[rx] > comp_size[ry]:
    comp_size[rx] += comp_size[ry]
    root[ry] = rx
  else:
    comp_size[ry] += comp_size[rx]
    root[rx] = ry
  return 1
  
answer = 0
for e in edge:
  c, ab = e
  a, b = ab
  answer += c * merge(a, b)
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
XY = [list(map(int, input().split())) + [i + 1] for i in range(N)]

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)
### BUGGY CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += base*bai
        ans %= mod
        p *= 25
        p %= mod
        q = z[l+k-i-1]
        bai = bai*i*pow(i-l+1,mod-2,mod)
    print(ans)
    
if __name__=="__main__":
    main()


### FIXED CODE ###

import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    #q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*z[l+k-i]*bai
        ans %= mod
        p *= 25
        p %= mod
        #q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

a,b,k = map(int,input().split())
num = [i for i in range(a,b+1)]
ans = []
if len(num)<=k:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(k):
        ans.append(num[i])
    for i in range(k):
        ans.append(num[len(num)-i-1])
    ans = set(ans)
    ans = list(ans)
    ans.sort()
    for i in range(len(ans)):
        print(ans[i])


### FIXED CODE ###

import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

a,b,k = map(int,input().split())
ans = []
if b-a<=k:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        ans.append(i)
    for i in range(b-k+1,b+1):
        ans.append(i)
    ans = set(ans)
    ans = list(ans)
    ans.sort()
    for i in range(len(ans)):
        print(ans[i])
### BUGGY CODE ###

def main():
     count = 1
     s = list(input())
     for i in range(1,len(s)):
         for j in range(0,len(s)-i):
             flag = check(s[j:j+i+1])
             if not flag:
                 count+=1
     print(count)

def check(s):
    i = 0
    while i <(len(s)>>1):
        if s[i]!=s[-i-1]:
            return False
        return True

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
     s = list(input())
     count = int((len(s)*(len(s)-1))/2+1)
     dic = {}
     for i in range(len(s)):
         try:
             dic[s[i]].append(i)
         except Exception:
             dic[s[i]] = [i]

     for j in dic.values():
         count-=int((len(j)*(len(j)-1))/2)
     print(count)


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

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

h, w = map(int, input().split())
a = [[j == "#" for j in input()] for i in range(h)]
# for i in range(h):
#     a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

loop = 0
# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            loop += 1
            white -= 1

count = 0

add = 0
while 1:
    if white == 0:
        break
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])
                add += 1


print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
input=sys.stdin.readline

class SegmentTreeSet():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=self.tree[pos]|val
    while pos>1:
      pos=pos//2
      self.tree[pos]=self.tree[2*pos]|self.tree[2*pos+1]
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=ret|self.tree[r]
      r=(r-1)//2
      ret=ret|self.tree[l]
      l=(l+1)//2
    return ret

n,q=map(int,input().split())
arr=list(map(int,input().split()))
st=SegmentTreeSet(n,set())
for i in range(n):
    tmp=set()
    tmp.add(arr[i])
    st.update(i,tmp)
for _ in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    print(len(st.query(l,r)))


### FIXED CODE ###

import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m= map(int,input().split())

B = []
C = [0]*n
ans = 0
pna = 0
for i in range(m):
    A = list(map(str,input().split()))
    if ans == n:
        break
    if A[1]=="AC":
        if A[0] not in B :
            B.append(A[0])
            ans += 1
            pna += C[int(A[0])-1]
    if A[1]=="WA"  :
        C[int(A[0])-1] += 1 
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)