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

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    for i in range(N):
        heappush(q,(-A[i],0))

    for i in range(K):
        l, c = heappop(q)
        heappush(q,(l*(c+1)/(c+2),c+1))
    
    ans = 0
    while q:
        l,c = heappop(q)
        ans = max(ans,-l)
    print(math.ceil(ans))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import math

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if K == 0:
        print(max(A))
        exit()
    
    # 二分探索で答えxを求める
    MIN = 0
    MAX = max(A)

    while MAX - MIN > 1:
        MID = (MIN + MAX)//2
        cnt = 0
        for i in range(N):
            cnt += (A[i]-1)//MID
        if cnt <= K:
            MAX = MID
        else:
            MIN = MID
    print(MAX)

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

n,y = map(int, input().split())
y /= 1000
for i in range(int(y//10+1)):
    for j in range(int((y-i*10)//1+1)):
        c = n-i-j
        if c >= 0 and 10 * i + 5 * j + 1 * c == y:
            print(i,j,c)
            exit()
print(-1,-1,-1)

### FIXED CODE ###

n,y = map(int, input().split())
for i in range(min(n+1, y//10000+1)):
    for j in range(min(n-i+1, y//1000+1)):
        c = n-i-j
        if 10000 * i + 5000 * j + 1000 * c == y:
            print(i,j,c)
            exit()
print(-1,-1,-1)
### BUGGY CODE ###

N = int(input())
S = sorted([input() for i in range(N)])
T = sorted(list(set(S)))
count = [0] * len(T)
for i in range(len(T)):
    for j in range(N):
        if T[i] == S[j]:
            count[i] += 1
count_index = [k for k, l in enumerate(count) if l == max(count)]
for m in count_index:
    print(T[m])

### FIXED CODE ###

from collections import Counter
n = int(input())
S = [input() for _ in range(n)]

poll = Counter(S)
max_c = max(list(poll.values()))
ans = [k for k in poll.keys() if poll[k] == max_c]
ans.sort()
for a in ans:
     print(a)
### BUGGY CODE ###

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

for i in range(0, n):
  p[i]=(p[i]+1)*p[i]/(p[i]*2)#p[i]が期待値になった

m = 0
for j in range(0, n-k+1):
  if m>=sum(p[j:j+k]):
    m = m
  else:
    m = sum(p[j:j+k])

print(m)


### FIXED CODE ###

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

kouho=0
lis=[0]*n
lis[0]=(1+p[0])/2
for i in range(0,n):
  if i>=1:
    lis[i]=lis[i-1]+(1+p[i])/2
  if i==k-1:
    kouho=lis[i]
  if i>k:
    if lis[i]-lis[i-k]>kouho:
      kouho=lis[i]-lis[i-k]
print(kouho)
### BUGGY CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
from collections import deque
squares = deque()
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.appendleft(square)
ans = float('inf')
while squares:
    x1,x2,y1,y2 = squares.popleft()
    if x1==x2 or y1==y2:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)
### BUGGY CODE ###

x = int(input())
m = 100

import math
count = 0
while True:
    if m >= x:
        print(count)
        break
    x = math.floor(m * 1.01)
    count += 1
    


### FIXED CODE ###

x = int(input())
m = 100

count = 0
while m < x:
    m += m // 100
    count += 1

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

s = input()
q = int(input())
status = 1
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        status *= -1
    else:
        if (query[1] == "1" and status == 1) or (query[1] == "2" and status == -1):
            s = query[2] + s
        else:
            s = s + query[2]

print(s if status == 1 else s[::-1])


### FIXED CODE ###

s = input()
q = int(input())
status = 1
top = []
bottom = []
for i in range(q):
    query = [i for i in input().split()]
    if query[0] == "1":
        status *= -1
    else:
        if (query[1] == "1" and status == 1) or (query[1] == "2" and status == -1):
            top.append(query[2])
        else:
            bottom.append(query[2])

tmp = "".join(top[::-1]) + s + "".join(bottom)
print(tmp if status == 1 else tmp[::-1])
### BUGGY CODE ###

n = int(input())
s = input()
cnt =0
r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  if s[i] == 'G':
    g.append(i)
  if s[i] == 'B':
    b.append(i)
for i in range(len(r)):
  for j in range(len(g)):
    for k in range(len(b)):
      a = sorted([r[i],g[j],b[k]])
      if a[2]-a[1] != a[1]-a[0]:
        cnt += 1
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
b=S.count('B')
g=S.count('G')
ans=r*b*g
for i in range(N):
    for s in range(N):
        j=i+s
        k=j+s
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

N =int(input())
S = str(input())
A = 0
R = []
G = []
B = []
for i in range(len(S)):
  if S[i] == "R":
    R.append(i+1)
  elif S[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)
#print(R)
#print(G)
#print(B)

for r in R:
  for g in G:
    for b in B:
      C = sorted([r,g,b])
      if C[1] - C[0] != C[2] - C[1]:
        A += 1
print(A)


### FIXED CODE ###

N =int(input())
S = str(input())
A = 0
R = []
G = []
B = []
for i in range(len(S)):
  if S[i] == "R":
    R.append(i+1)
  elif S[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

A = len(R)*len(G)*len(B)
for i in range(N):
  for j in range(i+1,N):
    k = j + (j-i)
    if k >= N:
      break
    if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
      A -= 1
print(A)
### BUGGY CODE ###

import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

af=collections.Counter(A)
res2=list(af.items())
res3=[0]*n
s=0
for i in range(0,len(res2)):
    s=s+com(res2[i][1],2)
for j in range(0,len(res2)):
    res3[res2[j][0]-1]=s-com(res2[j][1],2)+com(res2[j][1]-1,2)
for i in range(n):
    res[i]=res3[A[i]-1]

for j in range(n):
    print(res[j])

### FIXED CODE ###

import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

af=collections.Counter(A)
res2=list(af.items())
res3=[0]*n
s=0
for i in range(0,len(res2)):
    s=s+com(res2[i][1],2)
for j in range(0,len(res2)):
    res3[res2[j][0]-1]=s-res2[j][1]+1
for i in range(n):
    res[i]=res3[A[i]-1]

for j in range(n):
    print(res[j])
### BUGGY CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)


### FIXED CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)
### BUGGY CODE ###

X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [['' for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + X[i]
        else:
            if len(dp[i][j + 1]) > len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i][j + 1]
            else:
                dp[i + 1][j + 1] = dp[i + 1][j]

print(dp[x][y])
# print(dp)

### FIXED CODE ###

# educational DP contest F

X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

# print(dp[x][y])

ans = ''
while x > 0 and y > 0:
    if dp[x][y] == dp[x][y - 1]:
        y -= 1
    elif dp[x][y] == dp[x - 1][y]:
        x -= 1
    else:
        ans += X[x - 1]
        x -= 1
        y -= 1

print(ans[::-1])
### BUGGY CODE ###

N=int(input())
sn=[input() for _ in range(N)]
def check(s1,s2):
  a=list(s1)
  b=list(s2)
  a.sort()
  b.sort()
  if a==b:
    return True
  else:
    return False
  
cnt=0
for i in range(len(sn)-1):
  m=1
  if not sn[i]:continue
  for ii in range(i+1,len(sn)):
    if sn[ii] and check(sn[i],sn[ii]):
      cnt+=m
      m+=1
      sn[ii]=None

print(cnt)

### FIXED CODE ###

N=int(input())
dict={}
for _ in range(N):
  s=''.join(sorted(input()))
  dict[s]=dict.setdefault(s,0)+1
  
cnt=0
for c in dict.values():
  cnt+=(1+c-1)*(c-1)//2
  
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                row[j] = max(pr_j, r_j1)
#                if pr_j >= r_j1:
#                    row[j] = pr_j
#                else:
#                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(input())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = list(map(int, input().split()))

ans = 0
for c in C:
    max_index_B = bisect_left(B, c)
    for i in range(max_index_B):
        ans += bisect_left(A, B[i])

print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    max_index_A = bisect_left(A, b)
    max_index_C = N - bisect_right(C, b)
    ans += (max_index_A) * (max_index_C)

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

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

count = 0

for i in range(n):
  for j in range(i+1,n):
    a = l_li[i]
    b = l_li[j]
    wa = a + b
    sa = a - b
    if sa < 0:
      sa = -1 * sa
    for k in range(j+1,n):
      c = l_li[k]
      if c <= sa or c >= wa:
        continue
      count += 1
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l_li = [int(x) for x in input().split()]
l_li.sort()

count = 0
  
for i in range(n):
  for j in range(i+1,n):
    wa = l_li[i] + l_li[j]
    count += bisect.bisect_left(l_li, wa) - j - 1
    
print(count)
### BUGGY CODE ###

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

n = int(input())
a = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

remain_games = n * (n-1) // 2
ans = 0
while remain_games:
    flag = [0] * n
    update = False
    for i in range(n):
        if len(a[i]) == 0 or len(a[ a[i][0] ]) == 0:
            continue
        if flag[i] == 0 and a[ a[i][0] ][0] == i and flag[ a[i][0] ] == 0:
            b = a[i].popleft()
            _ = a[b].popleft()
            flag[i] = 1
            flag[b] = 1
            remain_games -= 1
            # print(ans, i, b)
            update = True
    if not update:
        ans = -1
        break
    ans += 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

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

# -*- coding: utf-8 -*-

# N: 買う品物の個数
# M: 持っている割引券の数
N, M = list(map(int, input().split()))

# X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を (X/2^Y) 円(小数点以下切り捨て)で買うことができます。
# 最小で何円あれば全ての品物を買うことができるのか?

# アイディア
# 単に高い商品から順に割引券を使えればよい...
# ただ、割引券は 10^5 枚ありえるようなので、
# 普通に並び替えて最大なものに割引券を適用する...というのを繰り返しても、
# タイムアウトになるだろう。
# うーん...
#
# 単に大きい順にソートして割引券を適用して、
# そのあとは挿入ソートを使って順繰りに割引券を適用するというのはどうだろうか
# やってみようか
A = list(map(int, input().split()))
A.sort(reverse=True)

# for i in range(M):
#     A[0] = A[0] / 2
#     A.sort(reverse=True)

for i in range(M):
    # 1. 先頭を半額にする
    # 2. 挿入ソートする
    A[0] = A[0] / 2

    if 1 < N:
        idx = 0
        for j in range(1, N):
            if A[j] < A[0]:
                idx = j
                break
        if idx == 0:  # A[0] より小さい値を探せなかったとき; 単に A[0] を最後尾に回す
            pass
            A = A[1:] + [A[0]]
        else:
            A = A[1:idx] + [A[0]] + A[idx:]

print(sum([int(x) for x in A]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

# N: 買う品物の個数
# M: 持っている割引券の数
N, M = list(map(int, input().split()))

# X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を (X/2^Y) 円(小数点以下切り捨て)で買うことができます。
# 最小で何円あれば全ての品物を買うことができるのか?

# アイディア
# 単に高い商品から順に割引券を使えればよい...
# プライオリティキューを使って最大のものから順次割引していけばよさそう
# Python のプライオリティキューは最小値しか取れないため、すべての値を (* -1) して考える (出力時にまた (* -1) して戻す)
A = [-x for x in map(int, input().split())]
heapq.heapify(A)


for i in range(M):
    # M 回割引券を適用する
    minimal = heapq.heappop(A)
    heapq.heappush(A, minimal / 2)

print(sum([int(x) for x in A]) * -1)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
s = sum(arr)
for _ in range(k):
    v = 0
    a,b = map(int, input().split())
    for i in range(len(arr)):
      if arr[i] == a:
        arr[i] = b
        v += 1
    s = s - (a*v) + (b*v)
    print(s)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
s = sum(arr)
d = {}
for i in arr:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for _ in range(k):
    v = 0
    a,b = map(int, input().split())
    if a not in d:
        print(s)
        continue
    s += (b-a) * d[a]
    if b in d:
        d[b] += d[a]
    else:
        d[b] = d[a]
    print(s)
    del d[a]
### BUGGY CODE ###

N = int(input())
s = input()

result = 0

def check(l):
    for start in range(N - 2*l + 1):
        if s[start:start+l] in s[start+l:]:
            return True
    else:
        return False

mn = 0
mx = N // 2 + 1

while mx - mn != 1:
    md = (mn + mx) // 2
    if check(md):
        mn = md
    else:
        mx = md

print(mn)


### FIXED CODE ###

import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))
### BUGGY CODE ###

s = input()

ans = 0
for i in range(len(s) - 3):
    for j in range(i + 3, len(s)):
        num = int(s[i:j + 1])
        if num % 2019 == 0:
            ans += 1

print(ans)


### FIXED CODE ###

s = input()
n = len(s)

mod = 2019
cnt = [0] * mod
cnt[0] = 1
digit = 1
now = 0

for i in range(1, n + 1):
    now += int(s[-i]) * digit
    digit *= 10
    digit %= mod
    now %= mod
    cnt[now] += 1

ans = 0
for i in cnt:
    ans += i * (i - 1) // 2

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

class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod

    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod

    def permutation(self, n, r):
        return self.factorial(n) * self.invfactorial(n-r) % self.mod

    def factorial(self, i):
        return self.fac[i]

    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    c = Combination(n+k)
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    p25[0], p26[0] = 1, 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod

    ans = 0
    for i in range(k+1):
        tmp = c.combination(n+k-i-1, n-1)
        tmp *= p25[k-i]
        tmp %= mod
        tmp *= p26[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    c = [0]*(k+1)

    p25[0], p26[0] = 1, 1
    c[0]= 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod
        c[i] = (n+i-1)*c[i-1]
        c[i] *= pow(i, mod-2, mod)
        c[i] %= mod
    p25.reverse()
    c.reverse()
    ans = 0
    for i in range(k+1):
        tmp = p25[i]*p26[i]*c[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


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

S=input()
length=len(S)
S=int(S)
count={}

for i in range(length+1):
    mod=(S%(10**i))%2019
    count[mod]=count.get(mod,0)+1


retval=0
for key in count:
    retval+=count[key]*(count[key]-1)//2

print(retval)


### FIXED CODE ###

from functools import lru_cache



S=input()
count=[0 for i in range(2019)]
length=len(S)
#S=int(S)
S=S+'0'
S=S[::-1]
_S=0

base=1
for i,s in enumerate(S):
    _S=base*int(s)+_S
    count[_S%2019]+=1
    base*=10
    base=base%2019
    _S=_S%2019



retval=0
for key in range(2019):
    retval+=count[key]*(count[key]-1)//2


print(retval)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
    p[i]=(p[i]+1)/2
q=[]
for i in range(n-k+1):
    q.append(sum(p[i:k+i]))
print(max(q))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
    p[i]=(p[i]+1)/2
q=[0]*(n-k+1)
q[0]=sum(p[0:k])
for i in range(1,n-k+1):
    q[i]=q[i-1]-p[i-1]+p[k+i-1]
print(max(q))
### BUGGY CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(ravel((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

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

mp = 1
EvenOdd = ""
sm = 0
for i in range(len(a)):
    sm += abs(a[i])
    mp *= a[i]
if mp < 0:
    min_a = min(abs(a[i]) for i in range(len(a)))
    print(sm - min_a*2)        
else:
    print(sm)

### FIXED CODE ###

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

abs_a = list(map(abs, a))
sm_abs_a = sum(abs_a)
min_a = min(abs(a[i]) for i in range(len(a)))

cnt = 0
for i in range(len(a)):
    if a[i] < 0:
        cnt += 1

if cnt%2 == 0:
    print(sm_abs_a)
else:
    print(sm_abs_a - min_a*2)