Problem:
Merge Sort Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function. Merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  create array L[0...n1], R[0...n2]
  for i = 0 to n1-1
    do L[i] = A[left + i]
  for i = 0 to n2-1
    do R[i] = A[mid + i]
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right) Input In the first line n is given. In the second line, n integers are given. Output In the first line, print the sequence S. Two consequtive elements should be separated by a space character. In the second line, print the number of comparisons. Constraints  n ≤ 500000  0 ≤ an element in S ≤ 10 9  Sample Input 1 10
8 5 9 2 6 3 7 1 10 4 Sample Output 1 1 2 3 4 5 6 7 8 9 10
34 Notes

Solution (Python):
INF = 10 ** 10

def merge(A, left, mid, right):
    c = 0
    n1 = mid - left
    n2 = right - mid
    Left = [A[left+i] for i in range(n1)]
    Right = [A[mid+i] for i in range(n2)]
    Left.append(INF)
    Right.append(INF)
    i=0
    j=0
    for k in range(left, right):
        c += 1
        if Left[i] <= Right[j]:
            A[k] = Left[i]
            i += 1
        else:
            A[k] = Right[j]
            j += 1
    return c

def mergeSort(hoge, left, right):
    c = 0
    if left+1 < right:
        mid = (left + right) // 2
        c += mergeSort(hoge, left, mid)
        c += mergeSort(hoge, mid, right)
        c += merge(hoge, left, mid, right)
    return c

if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    c = mergeSort(hoge, 0, len(hoge))
    print (' '.join([str(x) for x in hoge]))
    print (c)

Solution (Python):
def merge(A, left, mid, right):
    global c
    L=A[left:mid]+[1e10]
    R=A[mid:right]+[1e10]
    i=j=0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
        c+=1
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
c=0
n=int(input())
A=list(map(int,input().split()))
mergeSort(A, 0, n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L=A[l:m]+[1e10]
 R=A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m)
  s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Solution (Python):
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
import sys
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,sys.stdin.readline().split()))))
print(c)

Solution (Python):
import sys
def m(L,R):
 global c
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
  c+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,sys.stdin.readline().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:yield L[i];i+=1
  else:yield R[j];j+=1
  c+=1
def d(A):
 s=len(A)//2
 if len(A)>1:A[:]=m(d(A[:s])+[1e9],d(A[s:])+[1e9])
 return A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:yield L[i];i+=1
  else:yield R[j];j+=1
  c+=1
def d(A):
 s=len(A)//2
 if len(A)>1:A[:]=m(d(A[:s])+[1e9],d(A[s:])+[1e9])
 return A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:yield L[i];i+=1
  else:yield R[j];j+=1
  c+=1
def d(A):
 s=len(A)//2
 if len(A)>1:A[:]=m(d(A[:s])+[1e9],d(A[s:])+[1e9])
 return A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c
 i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:yield L[i];i+=1
  else:yield R[j];j+=1
  c+=1
def d(A):
 s=len(A)//2
 if len(A)>1:A[:]=m(d(A[:s])+[1e9],d(A[s:])+[1e9])
 return A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j<len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j<len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j<len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j<len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j<len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j<len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j<len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j<len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[];j=0
 for l in L:
  while j-len(R)and R[j]<l:T+=[R[j]];j+=1
  T+=[l]
 while j-len(R):T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 T+=R[::-1]
 return T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=0
n=int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c)

Solution (Python):
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
if'__main__'==__name__:
 c=-int(input())
 print(*d(list(map(int,input().split()))))
 print(c)