B. White Stone Creek
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ piles of stones, each pile initially containing exactly one stone.

You can perform some operations on them: choose a position $$$p$$$ ($$$1 \leq p \leq n$$$), then:

  • If $$$p = 1$$$, take one stone from pile $$$2$$$ and put it into pile $$$1$$$ (pile $$$2$$$ must have at least $$$1$$$ stone).
  • If $$$p = n$$$, take one stone from pile $$$n-1$$$ and put it into pile $$$n$$$ (pile $$$n-1$$$ must have at least $$$1$$$ stone).
  • If $$$2 \leq p \leq n-1$$$, take one stone from pile $$$p-1$$$ and one stone from pile $$$p+1$$$, and put them into pile $$$p$$$ (pile $$$p-1$$$ and pile $$$p+1$$$ must each have at least $$$1$$$ stone).

What is the minimum number of operations required so that, for all $$$1 \leq i \leq n$$$, pile $$$i$$$ contains exactly $$$a_i$$$ stones? It can be proved that when $$$\sum a_i = n$$$, there always exists a valid finite sequence of operations.In addition, sometimes you also need to output the sequence of operations.

Input

The first line contains two integers $$$n$$$, $$$\operatorname{typ}$$$ ($$$3 \leq n \leq 2 \times 10^5$$$, $$$\operatorname{typ} \in \{0,1\}$$$). $$$\operatorname{typ}$$$ indicates whether you need to output the sequence of operations.

The next line contains $$$n$$$ integers, representing $$$a_i$$$. It is guaranteed that $$$0 \leq a_i \leq n$$$ and $$$\sum a_i = n$$$.

Output

If $$$\operatorname{typ} = 0$$$, output a single integer, the answer.

If $$$\operatorname{typ} = 1$$$, you need to output two lines. The first line contains the answer $$$ans$$$. The second line contains $$$ans$$$ integers, where the $$$i$$$-th integer represents the position chosen for the $$$i$$$-th operation.

It is guaranteed that when $$$\operatorname{typ} = 1$$$, $$$ans$$$ does not exceed $$$2 \times 10^5$$$.

Examples
Input
5 1
0 2 1 2 0
Output
3
3 2 4
Input
10 0
0 0 5 2 2 1 0 0 0 0
Output
103