有 $n$ 堆石子，每堆初始时恰好有 $1$ 个石子。

你可以对它们进行一些操作：选择一个位置 $p$ ($1 \le p \le n$)，然后：

• 如果 $p = 1$，从第 $2$ 堆石子中取出一个石子并放入第 $1$ 堆（第 $2$ 堆必须至少有 $1$ 个石子）。
• 如果 $p = n$，从第 $n-1$ 堆石子中取出一个石子并放入第 $n$ 堆（第 $n-1$ 堆必须至少有 $1$ 个石子）。
• 如果 $2 \le p \le n - 1$，从第 $p - 1$ 堆和第 $p + 1$ 堆中各取出一个石子，并放入第 $p$ 堆（第 $p - 1$ 堆和第 $p + 1$ 堆必须各至少有 $1$ 个石子）。

要使对于所有 $1 \le i \le n$，第 $i$ 堆石子恰好包含 $a_i$ 个石子，最少需要多少次操作？可以证明，当 $\sum a_i = n$ 时，总是存在一个有效的有限操作序列。此外，有时你还需要输出该操作序列。

输入格式

第一行包含两个整数 $n, typ$ ($3 \le n \le 2 \times 10^5$, $typ \in \{0, 1\}$)。$typ$ 表示你是否需要输出操作序列。

第二行包含 $n$ 个整数，表示 $a_i$。保证 $0 \le a_i \le n$ 且 $\sum a_i = n$。

输出格式

如果 $typ = 0$，输出一个整数，即答案。

如果 $typ = 1$，你需要输出两行。第一行包含答案 $ans$。第二行包含 $ans$ 个整数，其中第 $i$ 个整数表示第 $i$ 次操作所选择的位置。

保证当 $typ = 1$ 时，$ans$ 不超过 $2 \times 10^5$。

样例

输入 1

5 1
0 2 1 2 0

输出 1

3
3 2 4

输入 2

10 0
0 0 5 2 2 1 0 0 0 0

输出 2

103