你拥有几顶帽子，其中有些你戴的频率比其他的高。由于同时戴上所有 $n$ 顶帽子是不切实际的，你将备用的帽子存放在一个有 $n-1$ 个挂钩的架子上。第一个挂钩距离门口 0.5 米，第二个距离 1 米，第三个距离 1.5 米，以此类推。这意味着从门口走到第 $i$ 个挂钩并返回需要走 $i$ 米。

今晚你需要进行一系列的公开露面，每次都需要佩戴适合该角色的头饰。当你从一次活动回来时，你会从挂钩上取下你需要的帽子，并与你之前戴的那顶帽子进行交换。这意味着随着夜晚的进行，帽子在架子上的位置会发生变化。

给定今晚的计划，并假设你已经戴上了第一顶帽子，为了使行走的距离之和最小，出发前在架子上排列帽子的最佳方式是什么？

输入格式

• 第一行包含两个整数：$c$ 和 $n$ ($1 \le c, n \le 10^5$)，分别表示帽子的总数和行程的长度。
• 第二行包含 $n$ 个整数：$v_1 \dots v_n$ ($1 \le v \le c; v[i] \neq v[i-1]$)，表示你需要佩戴的帽子顺序。你已经戴上了第一顶帽子，且你从不需要连续两次佩戴同一顶帽子。

输出格式

输出优化帽子架后你需要行走的最小距离。

接下来，输出 $c-1$ 个整数：一种能使行走距离最小的初始帽子架排列方式，从第 1 个位置开始。这应该包含除第一顶帽子之外的所有帽子，且每顶帽子恰好出现一次。

如果有多种正确的答案，你可以输出其中任意一种。

样例

输入 1

3 5
1 3 2 3 2

输出 1

5
2 3

输入 2

5 9
1 4 2 3 5 2 5 2 5

输出 2

14
3 5 4 2

Figure 1. 帽子架