Wstęp do programowania w C++

Napisz program, który wczyta ilość liczb (nie więcej niż 100), a następnie wczyta te liczby. Program powinien posortować liczby malejąco przy użyciu sortowania bąbelkowego (bubble sort), wypisać posortowaną listę oraz wypisać liczbę zamian wykonanych podczas sortowania.

Input

W pierwszym wierszu jedna liczba całkowita n (1 ≤ n ≤ 100) – liczba elementów.

W drugim wierszu n liczb całkowitych oddzielonych spacją.

Output

W pierwszym wierszu n posortowanych liczb w kolejności malejącej.

W drugim wierszu jedna liczba – ilość zamian wykonanych podczas sortowania.

Example

Input:

5
4 2 5 1 3
Output:

5 4 3 2 1
4