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

import sys


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0

    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            for dsn in (1, -1, N, -N):
                div, mod = divmod(qsn, N)
                if mod == 0 and dsn == -1: continue
                if mod == N - 1 and dsn == 1: continue
                if div == 0 and dsn == -N: continue
                if div == N - 1 and dsn == N: continue

                cdsn = qsn + dsn
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

N = input()
count=0
for i in range(len(N)+1):
  for j in range(i+1,len(N)+1):
    if(int(N[i:j])%2019==0):
      count+=1

print(count)

### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

q = int(input())
def solve(num):
    ans = pow(2, num-1, num)
    ANS = pow(2, (num+1)//2 -1, (num+1)//2)
    if num == 2:
        ans = 1
    if (num+1)//2 == 2:
        ANS = 1
    if num < 2:
        ans = 10**9
    if ans == 1 and ANS == 1:
        return 1
    else:
        return 0
dt = [list(map(int, input().split())) for _ in range(q)]
for i in range(q):
    l, r = dt[i]
    c = 0
    while l <= r:
        c += solve(l)
        l += 2
    print(c)

### FIXED CODE ###

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

def sosuu(num):
    Result = True
    for i in range(2, int(num**(1/2))+1):
        if num%i==0:
            Result = False
            break
    return Result #素数なら True

checker = [1 for i in range(10**5+1)]
checker[0] = 0
checker[1] = 0
for i in range(2, 10**5+1):
    if checker[i]:
        if sosuu(i):
            j = 2
            while i*j <= 10**5:
                checker[i*j] = 0
                j += 1
result = [0]
j = 0
for i in range(1, len(checker)):
    if checker[i] and checker[(i+1)//2]:
        j += 1
    result.append(j)

for l, r in lr:
    print(result[r]-result[l-1])
### BUGGY CODE ###

import numpy as np
N=int(input())
a=list(map(int, input().split(' ')))
a=int(np.prod(a))
count=0
while a%2==0:
    count+=1
    a=a/2
print(count)


### FIXED CODE ###

import numpy as np
N=int(input())
a=np.array(list(map(int, input().split(' '))))
count=0
i=1
while 2**i<a.max():
    count+=(a%(2**i)==0).sum()
    i+=1
print(count)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    S.append(Sh)
    
L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]=='.':
            a+=1
        else:
            a=0
        Lh=Lh+[a]
    L.append(Lh)

R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]=='.':
            a+=1
        else:
            a=0
        Rh=[a]+Rh
    R.append(Rh)

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]=='.':
            a+=1
        else:
            a=0
        Uw=Uw+[a]
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]
    
D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]=='.':
            a+=1
        else:
            a=0
        Dw=[a]+Dw
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

### FIXED CODE ###

import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)
### BUGGY CODE ###

def main():
    from decimal import Decimal

    N = int(input())
    *A, = map(Decimal, input().split())
    A = [x - i for i, x in enumerate(A, start=1)]
    A.sort()

    median = -1
    if N % 2 == 1:
        median = A[N // 2]
    else:
        median = (A[N // 2 - 1] + A[N // 2]) / 2  # ->ここで0.5が生じても偶数個足し合わせてintに戻る

    ans = sum(map(lambda x: abs(x - median), A))
    print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from statistics import median

n = int(input())
a = map(int, input().split())
a = tuple(sorted(x - i for i, x in enumerate(a, 1)))

# b = median(a)
b = a[n // 2]  # 要素が偶数個のとき、中央値の計算に使用する2値のいずれでもよい

ans = sum(abs(x - b) for x in a)
print(ans)
### BUGGY CODE ###

from functools import reduce
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
count = 0
set_s = list(set(s))
for i in range(len(set_s)):
    s_count = s.count(set_s[i])
    count += s_count * (s_count - 1) // 2
print(count)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
count = {}
ans = 0
for i in s:
    count[i] = count.get(i, 0) + 1
for key, value in count.items():
    ans += value * (value - 1) // 2
print(ans)
### BUGGY CODE ###

def solve():
  x,y,z,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  b = list(int(i) for i in input().split())
  c = list(int(i) for i in input().split())
  ab = []
  abc = []
  
  for i in range(x):
    for j in range(y):
      ab.append(a[i]+b[j])
  ab = sorted(ab,reverse = True)
  for t in range(min(k,len(ab))):
    for l in range(z):
      abc.append(ab[t]+c[l])
      
  abc = sorted(abc,reverse = True)
  for i in range(k):
    print(abc[i])

solve()

### FIXED CODE ###

def solve():
  x,y,z,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  b = list(int(i) for i in input().split())
  c = list(int(i) for i in input().split())
  a = sorted(a,reverse=True)
  b = sorted(b,reverse=True)
  c = sorted(c,reverse=True)
  ab = []
  abc = []
  
  for i in range(x):
    for j in range(y):
      ab.append(a[i]+b[j])
  ab = sorted(ab,reverse = True)
  for t in range(min(k,len(ab))):
    for l in range(z):
      abc.append(ab[t]+c[l])
      
  abc = sorted(abc,reverse = True)
  for i in range(k):
    print(abc[i])

solve()
### BUGGY CODE ###

import sys
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for i in range(n+1)] for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if X[i -1] == Y[j - 1]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i -1][j] >= c[i][j - 1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return str(c[m][n])

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))
                

### FIXED CODE ###

import sys
def lcs(X, Y):
    indices = [0]
    for c in Y:
        for i in range(len(indices) - 1, -1, -1):
            tmp = X.find(c, indices[i])
            if tmp + 1:
                if i + 1 < len(indices):
                    indices[i + 1] = min(indices[i + 1], tmp + 1)
                else:
                    indices.append(tmp + 1)
    return len(indices) - 1

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 1000000007
arr = np.arange(13, dtype = int)
dp = np.zeros([len(S), 13], dtype = int)

div13_list = [1]
for ii in range(1, len(S)):
    div13_list.append(div13_list[-1] * 10 % 13)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            # res = (((10 ** ii) * n) % 13 + arr) % 13
            res = (div13_list[ii] * n + arr) % 13
            dp[ii, res] += dp[ii - 1, arr]
            dp[ii, res] %= div_num
    else:
        # res = (((10 ** ii) * int(S[ind])) % 13 + arr) % 13
        res = (div13_list[ii] * int(S[ind]) + arr) % 13
        dp[ii, res] += dp[ii - 1, arr]
        dp[ii, res] %= div_num

print (dp[-1, 5])


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)
### BUGGY CODE ###

n = int(input())
a_list = []

for i in range(n):
    a = int(input())
    if a in a_list:
        a_list.remove(a)
    else:
        a_list.append(a)

print(len(a_list))


### FIXED CODE ###

n = int(input())
d = dict()
for i in range(n):
    a = int(input())
    if a in d:
        if d[a] == 0:
            d[a] = 1
        else:
            d[a] = 0
    else:
        d[a] = 1

print(sum(d.values()))
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

N,M = [int(a) for a in input().split()]
A = np.array([int(a) for a in input().split()])
#m_count = np.zeros(N, dtype=int)

for i in range(M):
    max_idx = np.argmax(A)
    #m_count[max_idx] += 1
    A[max_idx] /= 2

res = [int(a) for a in A]

print(sum(res))

### FIXED CODE ###

import sys
import heapq
from math import ceil

input = sys.stdin.readline

N,M = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

hq = []
for i in range(N):
    heapq.heappush(hq, -A[i])

for i in range(M):
    m = heapq.heappop(hq)
    heapq.heappush(hq, ceil(m / 2))

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]
a_dict = {}
for i in a:
    if i not in a_dict:
        a_dict[i] = 1
    else:
        a_dict[i] += 1
        
for b, c in bc:
    sumA = 0
    if b in a_dict:
        bn = a_dict[b]
        a_dict[b] = 0
        if c in a_dict:
            a_dict[c] += bn
        else:
            a_dict[c] = bn
    for k, v in a_dict.items():
        sumA += k*v
    print(sumA)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]

sumA = 0
num = [0]*100100
for aa in a:
    num[aa] += 1
    sumA += aa

for b, c in bc:
    sumA = sumA + ((c - b) * num[b])
    num[c] += num[b]
    num[b] = 0
    print(sumA)
### BUGGY CODE ###

N,M=map(int,input().split(" "))
#Nはポーンの数 Mは入力の数
A=list(map(int,input().split(" ")))
A=sorted(A)
L=[]
for s in range(M-1):
    L.append(A[s]-A[s+1])
if M<=N:
    print(0)
else:
    for s in range(N-1):
        L.remove(min(L))
    print(abs(sum(L)))

### FIXED CODE ###

N,M=map(int,input().split(" "))
A=list(sorted(map(int,input().split(" "))))
L=[A[s]-A[s+1] for s in range(M-1)]
if M>N:
    print(abs(sum(sorted(L)[N-1:])))
else:
    print(0)
### BUGGY CODE ###

import numpy as np
from fractions import gcd
 
 
N, M = list(map(int, input().split()))
S = input()
T = input()
N = len(S)
M = len(T)
s = []
t = []
L = int(N * M / gcd(N, M))
 
 
x = [0 for i in range(L)]
 
tmplen = N if N >= M else M
 
if tmplen == N:
    for i in range(tmplen):
        num = int(i * (L / N))
        x[num] = S[i]
    otherlen = M
    for j in range(otherlen):
        num = int(j * (L/M))
        if x[num] != 0 and x[num] != T[j]:
            L = -1
            break
else:
    for i in range(tmplen):
        num = int(i * (L / M))
        x[num] = T[i]
    otherlen = N
    for j in range(otherlen):
        num = int(j * (L/N))
        if x[num] != 0 and x[num] != S[j]:
            L = -1
            break
print(L)


### FIXED CODE ###

import numpy as np
from fractions import gcd
 
 
N, M = list(map(int, input().split()))
S = input()
T = input()

g = gcd(N, M)
l = int(N * M / g)

for i in range(g):
    if S[int(N/g*i)] != T[int(M/g*i)]:
        l = -1
        break

print(l)
### BUGGY CODE ###

n = int(input())
s = input()
# st = set()
# for i in range(n-2):
#     for j in range(i+1, n-1):
#         for k in range(j+1, n):
#             pin = s[i] + s[j] + s[k]
#             st.add(pin)
# print(st)
count = 0
# for i in range(1000):
#     if len(str(i)) == 1:
#         v = "00" + str(i)
#     elif len(str(i)) == 2:
#         v = "0" + str(i)
#     else:
#         v = str(i)
#     k = 0
#     for j in range(len(v)):
#         while k < len(s):
#             if s[k] == v[j]:
#                 k += 1
#                 break
#             k += 1
#         else:
#             break
#     else:
#         count += 1
for i in range(1000):
    v = [i // 100, (i // 10) % 10, i % 10]
    j = 0
    # print(v)
    for k in range(n):
        if s[k] == str(v[j]): j += 1
        if j == 3: break
    if j == 3: count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
# st = set()
# for i in range(n-2):
#     for j in range(i+1, n-1):
#         for k in range(j+1, n):
#             pin = s[i] + s[j] + s[k]
#             st.add(pin)
# print(st)
count = 0
# for i in range(1000):
#     if len(str(i)) == 1:
#         v = "00" + str(i)
#     elif len(str(i)) == 2:
#         v = "0" + str(i)
#     else:
#         v = str(i)
#     k = 0
#     for j in range(len(v)):
#         while k < len(s):
#             if s[k] == v[j]:
#                 k += 1
#                 break
#             k += 1
#         else:
#             break
#     else:
#         count += 1
for i in range(1000):
    v = [i // 100, (i // 10) % 10, i % 10]
    first = s[:-2].find(str(v[0]))
    if first == -1:
        continue
    second = s[first + 1:-1].find(str(v[1]))
    if second == -1:
        continue
    third = s[first + 1 + second + 1:].find(str(v[2]))
    if third == -1:
        continue
    # print(v, first, second, third, first + second +1)
    count += 1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
import heapq
import math

def main():
    N, K = map(int, input().split())
    A = [int(c) for c in input().split()]
    F = [int(c) for c in input().split()]
    
    A.sort()
    F.sort(reverse=True)

    num = 0
    sum_ = []
    for i in range(N):
      sum_.append(A[i] * F[i])
    left = 0
    right = 10 ** 12
    while(num < 100):
        number = 0
        mid = (left + right) // 2
        # print(mid)
        for i in range(len(A)):
            if sum_[i] <= mid:
                continue
            else:
                number += math.ceil((sum_[i] - mid) / F[i])
            # print(number)
        if number > K:
            # 最大値をmidより小さくできない -> 最大値はもっとでかい
            left = mid + 1
        else:
            right = mid
        num += 1
    print(mid)
                
        



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
import heapq
import math
 
def main():
    N, K = map(int, input().split())
    A = [int(c) for c in input().split()]
    F = [int(c) for c in input().split()]
    
    A.sort()
    F.sort(reverse=True)
 
    num = 0
    sum_ = []
    for i in range(N):
      sum_.append(A[i] * F[i])
    left = 0
    right = 10 ** 12
    while(num < 90):
        number = 0
        mid = (left + right) // 2
        # print(mid)
        for i in range(len(A)):
            if sum_[i] <= mid:
                continue
            else:
                number += math.ceil((sum_[i] - mid) / F[i])
            # print(number)
        if number > K:
            # 最大値をmidより小さくできない -> 最大値はもっとでかい
            left = mid + 1
        else:
            right = mid
        num += 1
    print(mid)
                
        
 
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import heapq
from math import ceil
N, K = list(map(int, input().split()))

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

hp = []

for log in A:
    heapq.heappush(hp, (-log, log, 1))

for i in range(K):
    cur_length, length, count = heapq.heappop(hp)
    cur_length = -cur_length
    new_length = length / (count + 1)
    heapq.heappush(hp, (-new_length, length, count + 1))

print(ceil(-hp[0][0]))



### FIXED CODE ###

from math import ceil
N, K = list(map(int, input().split()))

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

def possible(A, K, target):
    count = 0

    for a in A:
        count += ceil(a / target) - 1
    return count <= K

left = 1
right = max(A)

while left < right:
    mid = (left + right) // 2
    if possible(A, K, mid):
        right = mid
    else:
        left = mid + 1

print(right)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0

l=[A[0]]
for i in range(1,len(A)+1):
    l.append(sum(A[0:i+1]))
    if (l[i]-l[i-1])>2*l[i-1]:
        ans=0
    else:
        ans+=1

print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0

l=[A[0]]
for i in range(len(A)-1):
    l.append(l[-1]+A[i+1])
    if (l[-1]-l[-2])>2*l[-2]:
        ans=0
    else:
        ans+=1

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

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])

### FIXED CODE ###

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(2, S+1):
    if S % x == 0:
        if chk(x):
            ans = x
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(1, int(S**.5)+1):
    if S % x == 0:
        if chk(x):
            ans = max(ans, x)
        if chk(S // x):
            ans = max(ans, S // x)
print(ans)
### BUGGY CODE ###

#abc142C_go to school
N = int(input())
A = list(map(int, input().split()))
cnt =1
while cnt < N+1:
    for i in range(N):
        if A[i] == cnt:
            print(i+1,end=' ')
            cnt +=1
            break

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L.sort()
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = L[i][1]
print(*ans)
### BUGGY CODE ###

N = input()
N = int(N)
if not(1 <= N and N <= 10**9):
    exit()

# n_list = []
# num = 1
# for i in range(N):
#     n_list.append(i+1)
#     num = num * (i+1)

ans = 0
# i = 0
# for i in range(num):
#     print(i+1)
#     P = []

# print(n_list)



# ans = 0

# tmp = n_list.pop(0)
# n_list.append(tmp)
# print(n_list)

# for i in range(len(n_list)):
#     print((i+1)%n_list[i])
#     ans += (i+1) % n_list[i]

for i in range(N):
    ans += i+1
ans -= N

# P = []
# for i in n_list:
#     P.insert(0, i)

# print(P)
print(ans)

### FIXED CODE ###

N = input()
N = int(N)
if not(1 <= N and N <= 10**9):
    exit()
ans = 0

if N % 2 == 0:
    i = int(N/2)
    ans = (N+1) * i
    ans -= N
else:
    i = int(N/2)
    ans = N * i

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

import math

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

ans = 0

# p=1とp=2の期待値は変わらないことに注意
for i in range(n-k+1):
    total = 0
    for j in range(k):
        j += i
        total += sum([int(n) for n in range(1, pp[j]+1)])/pp[j]
    ans = max(ans, total)

print(ans)


### FIXED CODE ###

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

answer = sum(pp[:k])
total = sum(pp[:k])

for i in range(n-k):
    total = total - pp[i] + pp[i+k]
    answer = max(answer, total)

print((answer+k)/2)