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

import sys
sys.setrecursionlimit(10 ** 7)
S = input()

answer = 0

def F(s):
    global answer
    if len(s) <= 1:
        return
    if s[0] == 'x':
        if s[-1] == 'x':
            F(s[1:-1])
        else:
            answer += 1
            F(s[1:])
    else:
        if s[-1] == 'x':
            answer += 1
            F(s[:-1])
        elif s[0] == s[-1]:
            F(s[1:-1])
        else:
            print(-1)
            exit()

F(S)
print(answer)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
S = input()

answer = 0
left = 0
right = len(S) - 1
while left < right:
    if S[left] == S[right]:
        left += 1
        right -= 1
    elif S[left] == 'x':
        left += 1
        answer += 1
    elif S[right] == 'x':
        right -= 1
        answer += 1
    else:
        print(-1)
        exit()
print(answer)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x + y + z == S:
        ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for i in range(K + 1):
  for j in range(K + 1):
    if i + j == S:
      ans += 1
    elif 0 <= S - (i + j) <= K:
      ans += 1
print(ans)
### BUGGY CODE ###

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

scores=[]
for i in range(0,K):
    scores.append(A[i])

for j in range(K,N):
    if 0 in scores:
        scores.pop(0)
        scores.append(A[j])
        if 0 in scores:
            print("No")
        else:
            print("Yes")
    elif scores.pop(0)<A[j]:
        print("Yes")
        scores.append(A[j])
    else:
        print("No")
        scores.append(A[j])

### FIXED CODE ###

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

from collections import deque
scores=deque()

for i in range(0,K):
    scores.append(A[i])

for j in range(K,N):
#     if 0 in scores:
#         scores.pop(0)
#         scores.append(A[j])
#         if 0 in scores:
#             print("No")
#         else:
#             print("Yes")
    if scores.popleft()<A[j]:
        print("Yes")
        scores.append(A[j])
    else:
        print("No")
        scores.append(A[j])
### BUGGY CODE ###

n,q=(map(int,input().split()))
s=input()
count=0
for _ in range(q):
    l,r=(map(int,input().split()))
    for i in range(l,r):
        if s[i-1]=='A':
            if s[i]=='C':
               count+=1 
    print(count)
    count=0

### FIXED CODE ###

n,q=(map(int,input().split()))
s=input()
count=0
c=[0]*n
for i in range(1,n):
        if s[i-1]=='A':
            if s[i]=='C':
               count+=1
        c[i]=count
for _ in range(q):
    l,r=(map(int,input().split())) 
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

def digit_sum(n, s):
    if s > n:
        return -1
    if s == n:
        return n + 1

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

    p = int(n * 0.5)
    while p >= 1:
        b = (n - s) // p + 1
        if b > 1 and f(b, n) == s:
            return b
        
        p -= 1

    return -1


def f(b, n):
    if n < b:
        return n

    return f(b, n // b) + (n % b)

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()


### FIXED CODE ###

def digit_sum(n, s):
    if s > n:
        return -1
    if s == n:
        return n + 1

    b = 2
    while b**2 < n:
        if f(b, n) == s:
            return b

        b += 1

    p = int(n ** 0.5)
    while p >= 1:
        b = (n - s) // p + 1
        if b > 1 and f(b, n) == s:
            return b
        
        p -= 1

    return -1


def f(b, n):
    if n < b:
        return n

    return f(b, n // b) + (n % b)

def solve():
    n = int(input())
    s = int(input())
    result = digit_sum(n, s)
    print(result)

solve()
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(n):
    if i % 2 != n % 2:
        b.insert(0,a[i])
    else:
        b.append(a[i])

for _ in b:
    sys.stdout.write(str(_) + " ")
sys.stdout.write("\n")


### FIXED CODE ###

import sys
from collections import deque

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

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])

for _ in b:
    sys.stdout.write(str(_) + " ")
sys.stdout.write("\n")
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
        return
    if a[0] == 1:
        print(-1)
        return
    k = [(1<<i)-a[i] for i in range(n+1)]
    M = [1<<i for i in range(n+1)]
    for i in range(n):
        if k[i] <= 0:
            print(-1)
            return
        M[i+1] = min(M[i+1],k[i] << 1)
        k[i+1] = M[i+1] - a[i+1]
    if k[n] < 0:
        print(-1)
        return
    s = a[-1]
    ans = s
    for i in range(n)[::-1]:
        s = min(M[i],s+a[i])
        ans += s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
        return
    if a[0] == 1:
        print(-1)
        return
    k = 1-a[0]
    M = [1]
    p = 1
    for i in range(n):
        if k <= 0:
            print(-1)
            return
        M.append(min(p,k) << 1)
        k = M[i+1] - a[i+1]
        p <<= 1
    if k < 0:
        print(-1)
        return
    s = a[-1]
    ans = s
    for i in range(n)[::-1]:
        s = min(M[i],s+a[i])
        ans += s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import numpy as np

c = [[0]*3] * 3

for i in range(3):
    c[i] = list(map(int, input().split()))

c = np.array(c)

flg = False
for j in range(101):
    if (c[0] - j < 0).sum() >= 1:
        continue
    for k in range(101):
        if (c[1] - k < 0).sum() >= 1:
            continue
        for l in range(101):
            if (c[2] - l < 0).sum() >= 1:
                continue
            if (c[0] - j == c[1] - k).sum() == 3 and (c[1] - k == c[2] - l).sum() == 3:
                flg = True
                break

if flg:
    for j in range(101):
        if (c[:,0] - j < 0).sum() >= 1:
            continue
        for k in range(101):
            if (c[:, 1] - k < 0).sum() >= 1:
                continue
            for l in range(101):
                if (c[:, 2] - l < 0).sum() >= 1:
                    continue
                if (c[:, 0] - j == c[:,1] - k).sum() == 3 and (c[:,1] - k == c[:,2] - l).sum() == 3:
                    print("Yes")
                    exit()

print("No")



### FIXED CODE ###

import numpy as np

c = [[0]*3] * 3

for i in range(3):
    c[i] = list(map(int, input().split()))

c = np.array(c)

if len(set(c[0] - c[1])) == 1 and len(set(c[1] - c[2])) == 1 and len(set(c[:,0] - c[:,1])) == 1 and len(set(c[:,1] - c[:,2])) == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
    ans.append(str(a.index(i)+1))
ans=' '.join(ans)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans={}
for i in range(1,n+1):
    ans[a[i-1]]=i
answer=[]
for i in range(1,n+1):
    answer.append(str(ans[i]))
answer=' '.join(answer)
print(answer)
### BUGGY CODE ###

import collections
ans=0
N=int(input())
s_lst=[input() for _ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        si=collections.Counter(s_lst[i])
        sj=collections.Counter(s_lst[j])
        if si==sj:
            ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
d={}
ans=0
for i in range(N):
    s=''.join(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
a1 = 1
a2 = 1

for i in range(n):
    if i < k:
        a1 = a1*a[i]
    else:
        a2 = a1
        a1 = a[i]*a1//a[i-k]
        if a1 > a2:
            print('Yes')
        else:
            print('No')


### FIXED CODE ###

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

for i in range(n):
    if i < k:
        continue
    else:
        if a[i-k] < a[i]:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:], i8[:,:])')
def solve(N, costX, costY):
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = np.minimum(cx, cy).sum()
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    solve(N, costX, costY)

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

l = []

N = int(input())

for _ in range(N):
    A = int(input())
    if A in l:
        l.remove(A)
    else:
        l.append(A)

print(len(l))

### FIXED CODE ###

N = input()
N = int(N)

a_list = {}

ans = 0

for i in range(N):
    a = input()
    a = int(a)
    if a not in a_list:
        a_list[a] = 1
    else:
        a_list[a] = (a_list[a] + 1) % 2
    if a_list[a]:
        ans += 1
    else:
        ans -= 1

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

a=int(input())
b=list(map(int,input().split()))
c=b.copy()
d=0
e=[]
for m in range(a):
    tmp=0
    d+=1
    for i in range(m,len(b)):
        if d==b[i]:
            try:
                c.remove(b[i])
                tmp+=1
            except ValueError:
                break
    e.append(str(tmp))

f='\n'.join(e)
print(f)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
d=0
e=[0 for i in range(a)]


for i in range(len(b)):
    e[b[i]-1]+=1

for j in e:
    print(str(j))
### BUGGY CODE ###

import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, input().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        heapq.heappush(mins[uf.find(i)], a[i])
    if len(mins) == 1: return 0
    ans = 0
    for v in mins.values():
        ans += heapq.heappop(v)
    other_a = sorted(sum(mins.values(), []))
    return 'Impossible' if len(other_a) < len(mins) - 2 else ans + sum(other_a[:len(mins) - 2])

print(main())


### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
readline = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())
### BUGGY CODE ###

from sys import stdin
import re

S = stdin.readline().rstrip()

before_S = S

while(True):
    #after_S = S.replace("01", "").replace("10", "")
    after_S = re.sub("(01)+|(10)+", "", S)
    if len(after_S) != len(S):
        S = after_S
    else:
        break

print(len(before_S) - len(S))

### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()

stack = []
count = 0

for s in S:
    # スタックが空なら
    if not stack:
        stack.append(s)
    # スタックの一番上がsでなければ
    elif stack[-1] != s:
        stack.pop()
        count += 2
    else:
        stack.append(s)

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

import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, k = LI()
    g = defaultdict(list)
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    searched = [0 for i in range((n+1))]
    searched[s] = 1
    depth = [0 for i in range((n+1))]
    root = [0 for i in range((n+1))]
    ans = k
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if i == v:
                continue
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                root[i] = v
                searched[i] = 1
                if cand == 0:
                    print(0)
                    return
                ans *= cand % MOD
                cand -= 1
                Q.append(i)
    print(ans % MOD)






if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


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

n,k=map(int,input().split())
c=[]
for i in range(n):
  a,b=map(int,input().split())
  c+=[a]*b
c.sort()
print(c[k-1])

### FIXED CODE ###

n,K=map(int,input().split());c={}
for i in range(n):
  a,b=map(int,input().split())
  if a in c:c[a]+=b
  else:c[a]=b
for k,v in sorted(c.items()):
  K-=v
  if K<=0:print(k);exit()
### BUGGY CODE ###

num1, num2 = map(int, input().split())

n = max(num1, num2)
while(1):
  if n%num1==0 and n%num2==0:
    print(n)
    exit()
  n += 1

### FIXED CODE ###

num1, num2 = map(int, input().split())

import math
def gcd(num1, num2):
  for i in range(min(num1, num2),0,-1):
    if num1%i==0 and num2%i==0:
      return i
    
print(int(num1*num2/gcd(num1,num2)))
### BUGGY CODE ###

from collections import Counter
n = int(input())
Al = list(input().split())
count = Counter(Al)
for i in range(n):
    if str(i + 1) in Al:
        print(count[str(i+1)])
    else:
        print(0)

### FIXED CODE ###

from collections import Counter
n = int(input())
Al = list(input().split())
cdict = Counter(Al)
for i in range(n):
    print(cdict[str(i+1)])
### BUGGY CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
                DP[s] %= p
    print(DP[(1 << n)-1])


main()


### FIXED CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for _ in range(m):
    b, c= map(int, input().split())
    if a[n-1] < c:
        for i in range(min(b,n)):
            a.append(c)
        a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = sorted(list(map(int, readline().split())))
bc = [tuple(map(int, readline().split())) for i in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)
index = 0
cnt = 0
for i in range(n):
    if a[i] > bc[index][1]:
        break
    a[i] = bc[index][1]
    cnt += 1
    if cnt == bc[index][0]:
        cnt = 0
        index += 1
        if index == m:
            break
print(sum(a))
### BUGGY CODE ###

S = input()
n = int(input())
Q =[list(map(str, input().split())) for _ in range(n)]

for q in Q:
    if q[0] == "1":
        S = S[::-1]
    else:
        if q[1] == "1":
            S = q[2] + S
        else:
            S = S + q[2]
print(S)

### FIXED CODE ###

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

t = ''
for qi in Q:
  if int(qi[0]) == 1:
    s, t = t, s
  else:
    if int(qi[1])  == 1:
      t += qi[2]
    else:
      s += qi[2]
      
t = t[::-1]
t += s
print(t)
### BUGGY CODE ###

cnt = 0
def merge(A, left, mid, right):
  global cnt
  #print("marge ",A,left,mid,right)
  n1 = mid - left
  n2 = right - mid
  #L = [0] * (n1+1)
  #R = [0] * (n2+1)
  L = [0 for i in range(n1+1)]
  R = [0 for i in range(n2+1)]
  
  for i in range(int(n1)):
    L[i] = A[left + i]
  for i in range(int(n2)):
    R[i] = A[mid + i]
  L[n1] = 999999999
  R[n2] = 999999999
  i = 0
  j = 0
  for k in range(left,right):
    cnt+=1
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1

def mergeSort(A, left, right):
  #print("margeSort ",A,left,right)
  if left+1 < right:
    mid = int((left + right)/2)
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

n = int(input())
S = list(map(int,input().split()))
mergeSort(S, 0, n)
S = map(str, S)
print(' '.join(S))
print(cnt)


### FIXED CODE ###

cnt = 0
def merge(A, left, mid, right):
  global cnt
  #print("marge ",A,left,mid,right)
  n1 = mid - left
  n2 = right - mid
  #L = [0] * (n1+1)
  #R = [0] * (n2+1)
  L = [0] * (n1+1)
  R = [0] * (n2+1)
  
  for i in range(n1):
    L[i] = A[left + i]
  for i in range(n2):
    R[i] = A[mid + i]
  L[n1] = 999999999
  R[n2] = 999999999
  i = 0
  j = 0
  for k in range(left,right):
    cnt+=1
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1

def mergeSort(A, left, right):
  #print("margeSort ",A,left,right)
  if left+1 < right:
    mid = int((left + right)/2)
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

n = int(input())
S = list(map(int,input().split()))
mergeSort(S, 0, n)
S = map(str, S)
print(' '.join(S))
print(cnt)