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

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(8001 - distance[i])):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
        else:
            vert_sum += distance[i]
            for j in reversed(range(8001 - distance[i])):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    vert_last = 0
    side_last = 0
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(side_last+1)):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
            side_last += distance[i]
        else:
            vert_sum += distance[i]
            for j in reversed(range(vert_last+1)):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
            vert_last += distance[i]
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

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

#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)

a = np.zeros((h,w), dtype=np.int)
#print(yoko)

for i in range(h):
    temp = 0
    for j in range(w):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for i in range(h):
    temp = 0
    for j in range(w-1,-1,-1):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp
#print(a)
for j in range(w):
    temp = 0
    for i in range(h):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h-1,-1,-1):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp
answer=3
for i in range(h):
    for j in range(w):
        answer=max(a[i][j],answer)
#print(a)
print(answer-3)



### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)
b = np.array(grid)
b = np.where(b == ".", 1, 0)

a1 = np.zeros((h,w), dtype=np.int)
a2 = np.zeros((h,w), dtype=np.int)
a3 = np.zeros((h,w), dtype=np.int)
a4 = np.zeros((h,w), dtype=np.int)
#print(b)

for i in range(1,h):
    a1[i] += (a1[i-1]+1)*b[i-1]

for i in range(h-2,-1,-1):
    a2[i] += (a2[i+1]+1)*b[i+1]

for i in range(1,w):
    a3[:, i] += (a3[:, i-1]+1)*b[:, i-1]

for i in range(w-2,-1,-1):
    a4[:, i] += (a4[:, i+1]+1)*b[:, i+1]

#print(a1,a2,a3,a4)

answer = ( (a1+a2+a3+a4)*b ).max()

print(answer+1)
### BUGGY CODE ###

N = int(input())
A_i = list(map(int, input().split()))
for i in range(N):
    print(A_i.count(i + 1))


### FIXED CODE ###

N = int(input())
A_i = list(map(int, input().split()))
C = [0] * N
for i in A_i:
    C[i - 1] += 1
print(*C)
### BUGGY CODE ###

from collections import deque

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = []
    for i in range(h):
        a.append(list(input()))

    qu = deque()
    
    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.append((i, j))

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = deque()
        while len(qu) > 0:
            i0, j0 = qu.popleft()
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.append((ni, nj))
        qu = qu2
    print(ans)


### FIXED CODE ###

from collections import deque

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = []
    for i in range(h):
        a.append(list(input()))

    qu = deque()
    
    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.append((i, j))

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = deque()
        while len(qu) > 0:
            i0, j0 = qu.popleft()
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.append((ni, nj))
        qu = qu2
    print(ans)
### BUGGY CODE ###

INF = -1000000000000001

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

a = int(n/2)

dpa = [[INF for j in range(a+1)] for i in range(n+1)]

dpa[0][0] = 0
for i in range(1,n+1):
	dpa[i][0] = 0
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	elif i == 1:
		dpa[1][1] = l[0]
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

### FIXED CODE ###

from collections import defaultdict
INF = -1000000000000001

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

a = int(n/2)

dpa = defaultdict(lambda: -INF)
#dpa = [[0 for j in range(a+1)] for i in range(n+1)]

dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
		if (i != n):
			j += 1
#			print(i,j,dpa[(i,j)])
#			print("   ",i-2,j-1,dpa[(i-2,j-1)],"")
			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]

#print(dpa)
print(dpa[n,a])
### BUGGY CODE ###

a,b,c,d=map(int, input().split()) 
count =0

for i in range(a,b+1):
    if i%c==0 or i%d==0:
            count = count +1

print(b-a+1-count)

### FIXED CODE ###

import fractions
a,b,c,d=map(int, input().split()) 

i = b//c- (a-1)//c
j = b//d- (a-1)//d

f=fractions.gcd(c,d)
f2= int(c * d / f)
k = b//f2 - (a-1)//f2

pot = i + j - k

print(b-(a-1)-pot)
### BUGGY CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= -(-total//2):
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


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

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


from collections import defaultdict
dp = defaultdict(int)
dp[0]=0

for wv in wvList:
    w,v = wv
    tp = defaultdict(int,{ i[0]+w : i[1]+v  for i in dp.items() if i[0]+w<=W})
    for i in set(list(dp.keys())+list(tp.keys())):
        dp[i] = max(dp[i],tp[i])

print(max(dp.values()))

### FIXED CODE ###

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


from collections import defaultdict
dp = defaultdict(int)
dp[0]=0

for wv in wvList:
    w,v = wv
    tp = defaultdict(int,{ i[0]+w : i[1]+v  for i in dp.items() if i[0]+w<=W})
    for i in set(list(dp.keys())+list(tp.keys())):
        dp[i] = max(dp[i],tp[i])

print(max(dp.values()))
### BUGGY CODE ###

def divisors(m, n):
    divisors = [1]
    if m > n:
        m, n = n, m
    for i in range(2, m+1):
        if m % i == 0 and n % i == 0:
            divisors.append(i)
        while m % i == 0:
            m //= i
        while n % i == 0:
            n //= i
        if m == 1 or n == 1:
            break
    return divisors
m, n = map(int, input().split())
print(len(divisors(m, n)))

### FIXED CODE ###

a, b = map(int, input().split())
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

divisors = make_divisors(gcd(a, b))
ans = []
while divisors:
    key = divisors[0]
    ans.append(key)
    divisors.remove(key)
    notans = []
    for value in divisors:
        if gcd(key, value) != 1:
            notans.append(value)
    for i in notans:
        divisors.remove(i)
            
print(len(ans))
### BUGGY CODE ###

import bisect
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            bisect.insort(pys,j)
    if pys:
        sum+=pys.pop(-1)

print(sum)


### FIXED CODE ###

#import bisect
import heapq
from collections import deque
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
heapq.heapify(pys)
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            heapq.heappush(pys,-j)
    if pys:
        sum-=heapq.heappop(pys)

print(sum)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    S = list(map(int, list(readline().rstrip())))

    cnt = []
    pre = S[0]
    S.append(-1)
    c = 1
    for s in S[1:]:
        if s == pre:
            c += 1
        else:
            cnt.append(c)
            pre = s
            c = 1
    
    if S[0] == 0:
        cnt = [0] + cnt
    if S[-2] == 0:
        cnt.append(0)
    
    K = K * 2 + 1
    ans = sum(cnt[:K])
    for i in range(2, len(cnt)-K+1, 2):
        ans = max(ans, sum(cnt[i:i+K]))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    S = list(map(int, list(readline().rstrip())))

    cnt = []
    pre = S[0]
    S.append(-1)
    c = 1
    for s in S[1:]:
        if s == pre:
            c += 1
        else:
            cnt.append(c)
            pre = s
            c = 1
    
    if S[0] == 0:
        cnt = [0] + cnt
    if S[-2] == 0:
        cnt.append(0)
    
    K = K * 2 + 1
    ans = sum(cnt[:K])
    sc = ans
    for i in range(2, len(cnt)-K+1, 2):
        sc = sc - cnt[i-1] - cnt[i-2] + cnt[i+K-1] + cnt[i+K-2]
        ans = max(ans, sc)
    print(ans)

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

import sys
import math
import heapq

def input():
    return sys.stdin.readline().rstrip()



def dijkstra(s, n, es,L):
    #n:頂点数, es: 辺uvのコスト
    d = [10**14+7] * n
    #探索リスト
    S = [(0,s)]
    #優先度付きキューを使うと計算量が少なくなるよ
    heapq.heapify(S)
    used = [False] *n

    d[s] = 0

    while S:
        #最小コストの頂点を取り出し
        dg, v = heapq.heappop(S)
        if used[v] ==True:
            continue
        used[v] =True
        for u, w in es[v]:
            if d[v]%L + w >L:
                cost = d[v] - d[v]%L +L +w
            else:
                cost =d[v]+w

            if d[u] > cost:
                d[u] = cost
                heapq.heappush(S, (d[u],u))


        # print("d", d)
    return d




def main():
    N,M,L=map(int,input().split())

    es = [[] for _ in range(N)]

    for i in range(M):
        x, y, z = map(int, input().split())
        if z >L:
            continue
            
        x = x - 1
        y = y - 1
        es[x].append((y, z))
        es[y].append((x, z))  # 有向グラフの場合はこの行を消す

    answer = [[] for _ in range(N)]


    for i in range(N):
        d = dijkstra(i,N,es,L)
        answer[i] =d


    Q =int(input())
    for j in range(Q):
        s,t =map(int,input().split())
        a = answer[s-1][t-1]
        ans = a//L
        if a %L ==0:
            ans -=1
        if a ==10**14+7:
            print(-1)
        else:
            print(ans)


if __name__ == "__main__":
    main()

# \n


### FIXED CODE ###

import sys
import math
import heapq


def input():
    return sys.stdin.readline().rstrip()


def dijkstra(s, n, es, L):
    # n:頂点数, es: 辺uvのコスト
    d = [10 ** 14 + 7] * n
    # 探索リスト
    S = [(0, s)]
    # 優先度付きキューを使うと計算量が少なくなるよ
    heapq.heapify(S)
    used = [False] * n

    d[s] = 0

    while S:
        # 最小コストの頂点を取り出し
        dg, v = heapq.heappop(S)
        if used[v] == True:
            continue
        used[v] = True
        for u, w in es[v]:
            if d[v] % L + w > L:
                cost = d[v] - d[v] % L + L + w
            else:
                cost = d[v] + w

            if d[u] > cost:
                d[u] = cost
                heapq.heappush(S, (d[u], u))

        # print("d", d)
    return d


def main():
    N, M, L = map(int, input().split())

    dp = [[L+2]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] =0
    for i in range(M):
        x, y, z = map(int, input().split())
        if z > L:
            continue

        x = x - 1
        y = y - 1
        dp[x][y] =z
        dp[y][x]=z



    def warshal(ws,n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    ws[i][j] =min(ws[i][j],ws[i][k]+ws[k][j])
        return ws

    ls =warshal(dp,N)
    for i in range(N):
        for j in range(N):
            if ls[i][j] <=L:
                ls[i][j] =1
            else:
                ls[i][j] =500
    vs = warshal(ls,N)

    Q =int(input())

    for j in range(Q):
        s,t =map(int,input().split())
        ans = vs[s - 1][t - 1] - 1
        if ans >=N:
            print(-1)
        else:
            print(vs[s-1][t-1]-1)





if __name__ == "__main__":
    main()

# \n
### BUGGY CODE ###

from collections import deque
 
N, X, Y = map(int, input().split())
ans = [0 for i in range(N)]

dqs = [-1, 1]
for i in range(N-1):
  vis = [-1 for _ in range(N)]
  Q = deque([i])
  vis[i] = 0
  while Q:
    q = Q.popleft()
    for dq in dqs:
      if 0 <= q + dq < N:
      	if vis[q + dq] == -1:
          vis[q + dq] = vis[q] + 1
          Q.append(q + dq)
          if q + dq > i:
            ans[vis[q + dq]] += 1
    if q==X-1:
      if vis[Y-1] == -1:
        vis[Y-1] = vis[q] + 1
        Q.append(Y-1)
        if Y-1 > i:
          ans[vis[Y-1]] += 1
    if q==Y-1:
      if vis[X-1] == -1:
        vis[X-1] = vis[q] + 1
        Q.append(X-1)
        if X-1 > i:
          ans[vis[X-1]] += 1
for a in ans[1:]:
  print(a)

### FIXED CODE ###

from collections import deque
 
N, X, Y = map(int, input().split())
ans = [0 for i in range(N)]

dqs = [-1, 1]
for i in range(N-1):
  vis = [-1 for _ in range(N)]
  Q = deque([i])
  vis[i] = 0
  while Q:
    q = Q.popleft()
    for dq in dqs:
      if 0 <= q + dq < N:
      	if vis[q + dq] == -1:
          vis[q + dq] = vis[q] + 1
          Q.append(q + dq)
          if q + dq > i:
            ans[vis[q + dq]] += 1
    if q==X-1:
      if vis[Y-1] == -1:
        vis[Y-1] = vis[q] + 1
        Q.append(Y-1)
        if Y-1 > i:
          ans[vis[Y-1]] += 1
    if q==Y-1:
      if vis[X-1] == -1:
        vis[X-1] = vis[q] + 1
        Q.append(X-1)
        if X-1 > i:
          ans[vis[X-1]] += 1
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

a,b = map(int, input().split())
max = 0
arr = list(map(int, input().split()))
for i in range(a - b + 1):
  sum = 0
  for j in range(b):
    sum = sum + arr[i + j]
  if sum > max:
    max = sum
print((max + b) / 2)

### FIXED CODE ###

a,b = map(int, input().split())
max = 0
arr = list(map(int, input().split()))
cumsum = [0] * (a + 1)
for i in range(a):
  cumsum[i+1] = cumsum[i] + arr[i]
for i in range(a - b + 1):
  sum = 0
  sum = cumsum[i + b] - cumsum[i]
  if sum > max:
    max = sum
print((max + b) / 2)
### BUGGY CODE ###

import fractions
from functools import reduce
 
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
 
 
N = int(input())
a = list(map(int, input().split()))
ans = [0]*N
for i in range(0, N):
    tmp = a.pop(0)
    ans[i] = gcd_list(a)
    a.append(tmp)
 
ans.sort()
print(ans[N-1])

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
L = [0] * n
R = [0] * n
for i in range(1, n):
    L[i] = fractions.gcd(a[i - 1], L[i - 1])
    R[n - 1 - i] = fractions.gcd(a[n - i], R[n - i])
for i in range(0, n):
    ans[i] = fractions.gcd(L[i], R[i])
ans.sort()
print(ans[n - 1])
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
S=[]
B=[max(A), N]
for b in range(-max(B),max(B)):
    s=0
    for i in range(N):
        s+=abs(A[i]-b-i)
    S.append(s)
print(min(S))

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
u=[]
for i in range(N):
    u.append(A[i]-i)
a=sorted(u)
if len(a)%2==0:
    p=a[len(a)//2]
else:
    p=a[len(a)//2]
ans=0
for j in range(N):
    ans+=abs(a[j]-p)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))

count = 0
while count < M:
    As.sort(reverse=True)
    As[0] = int(As[0]/2)
    count += 1

print(sum(As))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
As = list(map(int, input().split()))
As = list(map(lambda x: -x, As))
heapq.heapify(As)

count = 0
while count < M:
    tmp = heapq.heappop(As)
    tmp = int(tmp/2)
    heapq.heappush(As, tmp)
    count += 1

print(-sum(As))
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
AAA = [int(i) for i in input().split()]

count = [0 for i in range(200010)]
for A in AAA:
    count[A]+=1
ans=0
while sum([1 if i!=0 else 0 for i in count])>K:
    #print(count[:10])
    buff = min([i for i in count if i!=0])
    ans += buff
    count.remove(buff)
print(ans)

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
AAA = [int(i) for i in input().split()]

count = [0 for i in range(200010)]
for A in AAA:
    count[A]+=1
ans=0
count=sorted([i for i in count if i!=0])

if len(count)<=K:
    print("0")
    exit()
else:
    print(sum(count[:-K]))
### BUGGY CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    S = input().rstrip()

    all = {'R','G','B'}

    R = []
    G = []
    B = []

    for i in range(N):
        temp = S[i]
        if temp == 'R':
            R.append(i)
        elif temp == 'G':
            G.append(i)
        else:
            B.append(i)

    res = len(R) * len(G) * len(B)

    count = 0

    for r in R:
        for g in G:
            for b in B:
                l = [r,g,b]
                l.sort()
                if l[1]-l[0] == l[2]-l[1]:
                    count += 1

    res -= count
    print(res)




main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    S = input().rstrip()

    R = set([])
    G = set([])
    B = set([])

    for i in range(N):
        temp = S[i]
        if temp == 'R':
            R.add(i)
        elif temp == 'G':
            G.add(i)
        else:
            B.add(i)

    all = [R,G,B]

    M = [len(R),len(G),len(B)]
    res = M[0] * M[1] * M[2]
    index = M.index(max(M))

    most = all.pop(index)
    first = all[0]
    second = all[1]

    count = 0

    for f in first:
        for s in second:
            temp1 = s * 2 - f
            temp2 = f * 2 - s
            temp3 = (f + s) // 2
            if (True) & (temp1 in most):
                count += 1
            if (True) & (temp2 in most):
                count += 1
            if (s + f) % 2 == 0:
                if temp3 in most:
                    count += 1

    res -= count
    print(res)




main()
### BUGGY CODE ###

N=int(input())
S=[]
for _ in range(N):
    s=input()
    #S.append("".join(sorted(s)))
    S.append(sorted(s))
#print(S)
re=0
for i in range(N-1):
    for j in range(i+1,N):
        if S[i]==S[j]:
            re+=1
            #break
print(re)


### FIXED CODE ###

N=int(input())
S=[]
for _ in range(N):
    s=input()
    S.append("".join(sorted(s)))
    #S.append(sorted(s))
#print(S)
re=0
dt={}
for i in range(N):
    if S[i] in dt:
        dt[S[i]]+=1
    else:
        dt[S[i]]=1
for v in dt.values():
    if v>=2:
        v-=1
        re+=(v*(v+1)//2)

print(re)