Sortowanie przez scalanie

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg liczb $a_1, a_2, \ldots, a_n$. Posortuj te elementy za pomocą algorytmu sortowania przez scalanie (ang. merge sort), tzn. zastosuj poniższy algorytm (jest to wersja algorytmu sortowania przez scalanie z wartownikami):

    \begin{algorithm}
    \caption{Sortowanie przez scalanie}
    \begin{algorithmic}
    \COMMENT{Cormen et al. \textit{Introduction to Algorithms}}
    
    \PROCEDURE{Merge}{$A, p, q, r$}
        \STATE $n1 \gets q-p+1$ \COMMENT{długość $A[p..q]$}
        \STATE $n2 \gets r-q$   \COMMENT{długość $A[q+1..r]$}
        \STATE
        \STATE create tables $L[0..n1], R[0..n2]$
        \STATE
        \STATE \COMMENT{skopiuj $A[p..q]$ do $L[0..n1-1]$}
        \FOR{$i \gets 0$ \TO $n1-1$}
            \STATE $L[i] \gets A[p+i]$
        \ENDFOR
        \STATE
        \STATE \COMMENT{skopiuj $A[q+1..r]$ do $R[0..n2-1]$}
        \FOR{$i \gets 0$ \TO $n2-1$}
            \STATE $R[i] \gets A[q+1+i]$
        \ENDFOR
        \STATE
        \STATE \COMMENT{ustaw wartowników}
        \STATE $L[n1] \gets \text{SENTINEL}$
        \STATE $R[n2] \gets \text{SENTINEL}$
        \STATE
        \STATE $i \gets 0$ \COMMENT{$i$ indeksuje najmniejszy pozostały element w $L$}
        \STATE $j \gets 0$ \COMMENT{$j$ indeksuje najmniejszy pozostały element w $R$}
        \STATE
        \FOR{$k \gets p$ \TO $r$}
            \IF{$L[i] \le R[j]$} \COMMENT{Ile razy wykona się ta instrukcja?}
                \STATE $A[k] \gets L[i]$
                \STATE $i \gets i+1$
            \ELSE
                \STATE $A[k] \gets R[j]$
                \STATE $j \gets j+1$
            \ENDIF
        \ENDFOR
    \ENDPROCEDURE
    \STATE
    \PROCEDURE{Merge–Sort}{$A, p, r$}
        \IF{$p \ge r$} \COMMENT{zero lub jeden element}
            \RETURN
        \ENDIF
        \STATE $q \gets (p + r) / 2$ \COMMENT{środek A[p..r]}
        \STATE \CALL{Merge–Sort}{$A, p, q$} \COMMENT{posortuj rekurencyjnie A[p..q]}
        \STATE \CALL{Merge–Sort}{$A, q+1, r$} \COMMENT{posortuj rekurencyjnie A[q+1..r]}
        \STATE \CALL{Merge}{$A, p, q, r$} \COMMENT{scal A[p..q] i A[q+1..r] do A[p..r]}
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy wiersz wyjścia zawiara posortowany ciąg $n$ elementów $a_i$ w kolejności niemalejącej. W drugim wierszu wypisz ile razy wykona się test L[i]<=R[j] we funkcji Merge.

Ograniczenia

• $1 \le n \le 500 000$
• $-10^9 \le a_i \le 10^9$

Przykłady

Wejście 1

10
8 5 9 2 6 3 7 1 10 4

Wyjście 1

1 2 3 4 5 6 7 8 9 10
34