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

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

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
d = n - l[1] + l[0]

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

mod = (10 ** 9 + 7)
tmp = 1
for k in range(1, n + 2):
    tmp = mul(tmp, n - k + 2)
    tmp = div(tmp, k)

    if k == 1:
        dc = 1
    elif d >= k - 1:
        dc = mul(dc, (d - k + 2))
        dc = div(dc, k - 1)
    else:
        dc = 0
    print((tmp - dc) % mod)


### FIXED CODE ###

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

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
    if len(l) == 2:
        break
d = n - l[1] + l[0]

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

mod = (10 ** 9 + 7)

N1 = n + 2
factorial1 = [1]
for i in range(1, N1):
    factorial1.append(factorial1[i - 1] * i % mod)
inverseFactorial1 = [0] * N1
inverseFactorial1[N1 - 1] = power(factorial1[N1 - 1], mod - 2)
for i in range(N1 - 2, -1, -1):
    inverseFactorial1[i] = inverseFactorial1[i + 1] * (i + 1) % mod
def combi1(x, y):
    return factorial1[x] * inverseFactorial1[y] * inverseFactorial1[x - y] % mod

for k in range(1, n + 2):
    if d >= k - 1:
        print((combi1(n+1, k) - combi1(d, k-1)) % mod)
    else:
        print(combi1(n+1, k))
### BUGGY CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10**6)
    s = input().strip()
    N = len(s)
    d = np.ones(N+1, dtype=int) * -10**5
    d[0] = 0
    for i, si in enumerate(s, start=1):
        d[1:i+1] = np.maximum(d[:i] - (si == 'p'), d[1:i+1] + (si == 'g'))
        # print('i={}, si={}'.format(i, si), d)
    print(max(d[N//2+N%2:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10**6)
    s = input().strip()
    N = len(s)
    p = sum([1 if si == 'p' else 0 for si in s])
    print(N//2-p)

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

import bisect
a,b,q=map(int,input().split())
S=[10**20];T=[10**20]
for _ in range(a):
    s=int(input())
    S.append(s)
for _ in range(b):
    t=int(input())
    T.append(t)
S.sort()
T.sort()

for _ in range(q):
    x=int(input())
    se=S[bisect.bisect_left(S,x)]
    sw=S[bisect.bisect_left(S,x)-1]
    te=T[bisect.bisect_left(T,x)]
    tw=T[bisect.bisect_left(T,x)-1]

    m1=abs(x-se)+abs(se-te)
    m2=abs(x-se)+abs(se-tw)
    m3=abs(x-sw)+abs(sw-te)
    m4=abs(x-sw)+abs(sw-tw)
    m5=abs(x-te)+abs(te-se)
    m6=abs(x-te)+abs(te-sw)
    m7=abs(x-tw)+abs(tw-se)
    m8=abs(x-tw)+abs(tw-sw)
    print(min(m1,m2,m3,m4,m5,m6,m7,m8)) 

### FIXED CODE ###

import bisect
a,b,q=map(int,input().split())
S=[];T=[]
for _ in range(a):
    s=int(input())
    S.append(s)
for _ in range(b):
    t=int(input())
    T.append(t)
S.append(10**12)
T.append(10**12)

for _ in range(q):
    x=int(input())
    idx_s=bisect.bisect_left(S,x)
    idx_t=bisect.bisect_left(T,x)
    se=S[idx_s]
    sw=S[idx_s-1]
    te=T[idx_t]
    tw=T[idx_t-1]

    ans=float("inf")
    for ss in [se,sw]:
        for tt in [te,tw]:
            ans=min(ans,abs(ss-x)+abs(tt-ss),abs(tt-x)+abs(tt-ss))
    print(ans)
### BUGGY CODE ###

n = int(input())

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

ans = 1

for i in range(n):
    ans = ans * a[i]


if(ans > 10**18):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

from collections import deque
import sys
n = int(input())

a = list(map(int,input().split()))
a.sort()
if(a[0] == 0):
    print("0")
    sys.exit()
ans = 1
for i in range(n):

    ans = ans * a[i]
    if(ans > 10**18):
        print("-1")
        sys.exit()
     




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

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

res = 0
for i in range(len(P)):
    if min(P[:i+1]) == P[i]:
        res += 1

print(res)

### FIXED CODE ###

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

res = 1

minP = P[0]
for i in range(len(P)-1):
    if minP > P[i+1]:
        minP = P[i+1]
        res += 1

print(res)
### BUGGY CODE ###

from collections import deque


def bfs(q):
    ans = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
                ans = max(ans, dist[ni][nj])
    return ans


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            dist[i][j] = 0
            q.append((i, j))
print(bfs(q))


### FIXED CODE ###

from collections import deque


def bfs(q):
    ans = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
                ans = max(ans, dist[ni][nj])
    return ans


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            dist[i][j] = 0
            q.append((i, j))
print(bfs(q))
### BUGGY CODE ###

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

count=0
l=sorted(L,reverse=True)

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if l[i]<l[j]+l[k]:
                count+=1



print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

from collections import deque

N,M = map(int,input().split())
edges = []
ad = [[] for _ in range(N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    ad[u].append(v)
    edges.append((u,v))
S,T = map(int,input().split())
S -= 1
T -= 1

dq = deque()
dq.append((S,0))
while dq:
    v,d = dq.popleft()
    nd = d + 1
    for nv in ad[v]:
        if nv == T and nd % 3 == 0:
            print(nd//3)
            exit()
        if d == 10**6:
            print(-1)
            exit()
        dq.append((nv,nd))

print(-1)

### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())
ad = [[[] for _ in range(3)] for _ in range(N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    for j in range(3):
        ad[u][j].append((v,(j+1)%3))
S,T = map(int,input().split())
S -= 1
T -= 1

visited = [[False]*3 for _ in range(N)]
dq = deque()
dq.append((S,0,0))
visited[S][0] = True

while dq:
    v,j,d = dq.popleft()
    nd = d + 1
    for nv,nj in ad[v][j]:
        if (nv,nj) == (T,0):
            print(nd//3)
            exit()
        if visited[nv][nj]:
            continue
        visited[nv][nj] = True
        dq.append((nv,nj,nd))
        
print(-1)
### BUGGY CODE ###

A,B,Q = map(int, input().split())
S = [int(input()) for i in range(A)]
T = [int(input()) for i in range(B)]
X = [int(input()) for i in range(Q)]


def bs(x, L, ub, lb):
    if x < L[0]:
        return -1
    if x > L[-1]:
        return len(L)-1
    c = (ub+lb)//2
    if ub-lb <= 1:
        return c
    if L[c] >= x:
        return bs(x, L, c, lb)
    else:
        return bs(x, L, ub, c)
    
for i in range(Q):
    s_l = bs(X[i], S, A-1, 0)
    t_l = bs(X[i], T, B-1, 0)
    
    if s_l < 0:
        sl = 10**11
        su = S[0]-X[i]
    elif s_l == A-1:
        sl = X[i]-S[s_l]
        su = 10**11
    else:
        sl = X[i]-S[s_l]
        su = S[s_l+1]-X[i]
        
    if t_l < 0:
        tl = 10**11
        tu = T[0]-X[i]
    elif t_l == B-1:
        tl = X[i]-T[t_l]
        tu = 10**11
    else:
        tl = X[i]-T[t_l]
        tu = T[t_l+1]-X[i]
    ans = min(max(su, tu), max(sl, tl), su*2+tl, tl*2+su, sl*2+tu, tu*2+sl)
    print(ans)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]

for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
point = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
done = [-1]*N
def dfs(cur, fr, p):
    done[cur] = p
    for nex in G[cur]:
        if nex == fr: continue
        dfs(nex, cur, p+point[nex])
dfs(0, -1, point[0])
ans = []
for i in range(N):
    ans.append(done[i])
print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
point = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
done = [-1]*N
def dfs(cur, fr, p):
    done[cur] = p
    for nex in G[cur]:
        if nex == fr: continue
        dfs(nex, cur, p+point[nex])
dfs(0, -1, point[0])
ans = []
for i in range(N):
    ans.append(done[i])
print(*ans)
### BUGGY CODE ###

def P(n,r):
  s = 1
  for i in range(r+1, n+1):
    s = s*i
  return s

def cmb(n,r):
  if n == r:
    return 1
  else:
    return P(n,r) // P(n-r,0)

N = int(input())
S = []
ans = 0
n = 1

for i in range(N):
  s = list(input())
  s.sort()
  S.append(s)

S.sort()

for i in range(N-1):
  if S[i] == S[i+1]:
    n += 1
  elif n >= 2:
    ans += cmb(n,2)
    n = 1
  else:
    n = 1
  
if S[N-1] == S[N-2]:
  ans += cmb(n,2)
  
print(ans)

### FIXED CODE ###

import collections

N = int(input())
S = []

for i in range(N):
  s = input()
  ss = [i for i in s]
  ss.sort()
  s = ''.join(ss)
  S.append(s)
  
c = collections.Counter(S)
ans = 0

for b in c:
  ans += c[b] * (c[b] - 1) // 2
  
print(ans)
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys

n,k = map(int, sys.stdin.readline().rstrip().split())
hn = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [-1] * n

dp[0] = 0
for i in range(1,n):
  for j in range(1,min(k+1,i+1)):
    ret = dp[i-j]+abs(hn[i-j]-hn[i])
    if (dp[i] > ret) or (dp[i] < 0):
      dp[i] = ret
print(dp[n-1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys
import numpy as np

n,k = map(int, sys.stdin.readline().rstrip().split())
h = np.array(list(map(int, sys.stdin.readline().rstrip().split())))

dp = np.zeros(n, dtype=np.int)

for i in range(1,n):
  if i < k:
    dp[i] = np.min(dp[:i] + np.abs(h[i]-h[:i]))
  else:
    dp[i] = np.min(dp[i-k:i] + np.abs(h[i]-h[i-k:i]))

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

from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys

#sys.stdin=open("./testfile1.py","r")
raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()

st=[]
s=f4()
n1=0
ans=0
for i in s:
	n1+=1
	st.append(i)
	if n1>=3:
		s1=""
		for i in xrange(3):
			s1+=st.pop()
		s1=s1[::-1]
		if s1=="ABC":
			ans+=1
			s1="BCA"
			while st and st[-1]=="A":
				s1+="A"
				ans+=1
				st.pop()
			st.extend(list(s1))

		else:
			st.extend(list(s1))

print ans


### FIXED CODE ###

from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys

#sys.stdin=open("./testfile1.py","r")
raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()
def main():
	
	s=f4()
	n1=0
	ans=0
	i=0
	while i<len(s)-1:
		if s[i]=="A":
			n1+=1
		elif s[i:i+2]=="BC":
			ans+=n1
			i+=1
		else:
			n1=0
		i+=1
	print ans

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
MOD = 10**9+7
 
N = int(input())
S = list(input())
 
if S[0] == "W" or S[-2] == "W":
    print(0)
    sys.exit()
 
S = [0 if i == "W" else 1 for i in S]
 
LR = [0 for i in range(2*N)]
count0 = 1
count0_raw = 1
ans = 1
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1
 
    if LR[i] == 0:
        count0 += 1
        count0_raw += 1
    else:
        ans *= count0 % MOD
        count0 -= 1
 
if count0_raw != N:
    print(0)
    sys.exit()
 
N_k = 1
for i in range(N):
    N_k = N_k*(i+1)%MOD 
 
print(ans*N_k%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

N = int(input())
S = list(input().rstrip())

if S[0] == "W" or S[-1] == "W":
    print(0)
    sys.exit()

LR = [0 for i in range(2*N)]
count0 = 1
count0_raw = 1
ans = 1
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1

    if LR[i] == 0:
        count0 += 1
        count0_raw += 1
    else:
        ans *= count0
        ans %= MOD
        count0 -= 1

if count0_raw != N:
    print(0)
    sys.exit()

N_k = 1
for i in range(N):
    N_k *= i+1
    N_k %= MOD

print(ans*N_k%MOD)
### BUGGY CODE ###

n = int(input())
X = list(map(int,input().split()))
h = int(n/2)
for i in range(n):
  xis = []
  if i != 0:
    xis += X[0:i]
    xis += X[i+1:n]
    print(sorted(xis)[h-1])
  else:
    xis = X[1:]
    print(sorted(xis)[h-1])

### FIXED CODE ###

n = int(input())
X = list(map(int,input().split()))
h = int(n/2)
Xs = sorted(X)
m1 = Xs[h-1]
m2 = Xs[h]

for i in range(n):
  if X[i] <= m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

n, m = map(int, input().split())
k = m // n
while m % k:
    k -= 1
print(k)

### FIXED CODE ###

n, m = map(int, input().split())
k = m
for i in range(1, int(m**0.5) + 1):
    if m % i:
        continue
    if i >= n:
        print(m // i)
        break
    if m // i >= n:
        k = i
else:
    print(k)
### BUGGY CODE ###

import bisect
n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i in range(n): b[a[i]-1] = i
ans,c = (b[0]+1)*(n-b[0]),[b[0]]
for i in range(1,n):
	x = bisect.bisect_left(c,b[i])
	if 0<x<len(c): ans += (c[x]-b[i])*(b[i]-c[x-1])*(i+1)
	elif x==0: ans += (c[0]-b[i])*(b[i]+1)*(i+1)
	elif x==len(c): ans += (b[i]-c[-1])*(n-b[i])*(i+1)
	bisect.insort_left(c,b[i])
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n): b[a[i]]=i
for i in range(n,0,-1):
	m = b[i]
	x,y = l[m],r[m]
	ans+=i*(m-x+1)*(y-m+1)
	l[y+1],r[x-1] = x,y
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
l = [i[0] for i in c.items() if i[1] == c.most_common()[0][1]]
l.sort()

for s in l:
  print(s)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
maxcnt = c.most_common()[0][1]
l = []
for i in c.most_common():
  if i[1] != maxcnt:
    break
  l.append(i[0])

for s in sorted(l):
  print(s)
### BUGGY CODE ###

import math

N,a,b=map(int,input().split())

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

M = pow(2, N)

c=1
d=1
for i in range(a):
  c*=(N-i)
  d*=i+1

e=1
f=1
for i in range(b):
  e*=(N-i)
  f*=i+1

print((M-1-c//d-e//f)%(10**9+7))

### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

INF = 10 ** 10
dp = [INF] * (10 ** 5 + 10)
H += [H[-1] * K]

dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k <= N:
            dp[i + k] = min(dp[i + k], dp[i] + abs(H[i + k] - H[i]))


print(dp[N-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

INF = 10 ** 10
dp = [INF] * (10 ** 5 + 10)
H += [H[-1] * K]

dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k <= N:
            dp[i + k] = min(dp[i + k], dp[i] + abs(H[i + k] - H[i]))


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

import numpy as np
N=int(input()) 
c=input()

#print(c.count('R'),c.count('W'))

ANS=np.zeros(N+1)

ANS[0]=c.count('R')
ANS[N]=c.count('W')

for i in range(1,N):
  ANS[i]=max(c[0:i].count('W'),c[i:N].count('R'))

print(int(min(ANS)))

### FIXED CODE ###

import numpy as np
N=int(input()) 
c=input()

#print(c.count('R'),c.count('W'))

ANS=np.zeros(N+1)
CR=np.zeros(N+1)
CW=np.zeros(N+1)

CR[0]=c.count('R')
CW[N]=c.count('W')

ANS[0]=c.count('R')
ANS[N]=c.count('W')


for i in range(1,N+1):
  if(c[i-1]=='R'):
    CR[i] = CR[i-1] - 1
    CW[i] = CW[i-1]
  else:
    CR[i] = CR[i-1]
    CW[i] = CW[i-1] + 1
  ANS[i]=max(CR[i],CW[i])

print(int(min(ANS)))
#print(CR,CW)
### BUGGY CODE ###

input()
s = input()

def f(i):
  return s[0:i].count('W') + s[i:].count('E')

x = len(s)

for i in range(len(s)):
  x = min(x, f(i))

print(x)

### FIXED CODE ###

input()
s = input()

l = 0
r = s[1:].count('E')
x = l + r

for i in range(1, len(s)):
  if s[i - 1] == 'W':
    l += 1

  if s[i] == 'E':
    r -= 1
  x = min(x, l + r)

print(x)
### BUGGY CODE ###

def main():
    A, B, K = map(int, input().split())
    all_nums = [x for x in range(A, B+1)]
    cond_nums = all_nums[:K]
    for n in all_nums[-K:]:
        if n not in cond_nums:
            cond_nums.append(n)
    for x in cond_nums:
        print(x)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    A, B, K = map(int, input().split())
    if B - A + 1 <= 2 * K:
        for i in range(A, B+1):
            print(i)
    else:
        for i in range(K):
            print(A+i)
        for i in range(K):
            print(B-K+1+i)


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

from heapq import *

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    n, m = read_int_array()
    nums = read_int_array()

    heapify(nums)
    for _ in range(m):
        b, c = read_int_array()
        while b and nums[0] < c:
            heapreplace(nums, c)
            b -= 1
    write(sum(nums))

main()


### FIXED CODE ###

from heapq import *

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    n, m = read_int_array()
    nums = read_int_array()

    heapify(nums)
    ops = [None]*m
    for i in range(m):
        b, c = read_int_array()
        ops[i] = (c, b)
    ops.sort(reverse=True)

    done = []
    for c, b in ops:
        while b and nums and nums[0] < c:
            heappop(nums)
            done.append(c)
            b -= 1
        if not nums or nums[0] >= c:
            break
    write(sum(nums) + sum(done))

main()