Background

Description

给定一个 1∼N 的随机排列，要求一次只能交换相邻两个数，那么最少需要交换多少次才可以使数列按照从小到大排列呢？ 请你求出一个待排序序列的最少交换次数和排完序后的升序数列

Format

Input

第一行一个整数 N。

第二行一个 1∼N的排列。

Output

第一行输出该升序数列，数之间用空格隔开

第二行输出最少交换次数。

Samples

8
4 8 2 7 5 6 1 3

1 2 3 4 5 6 7 8
18

Limitation

1≤N≤100