Help ssheep solve this problem!

Define the prefix of an array as a sub-array from the beginning of the array up to an index. For example, the prefix of index ~3~ of the array ~[1,2,3,4,5]~ would be ~[1,2,3]~.

Define a prefix query when you take a prefix of the array, ~A~, and multiply all the elements in the prefix with ~-1~. Essentially, this operation flips the signs of the elements.

Given an array of ~N~ integers, find the maximum sum of the elements you can obtain after performing prefix queries.

Since ssheep knows that there can be many ways to get the maximum sum, he wants to know the indices of the prefix queries. He also wants to have the least amount of queries, sorted in ascending order.

Input Specification

The first line will contain the integer ~1\leq N\leq10^5~, the number of elements of the array, ~a~.

The second line will contain ~N~ integers, the elements of the array, ~a_1,a_2,\ldots,a_N~ ~(-10^9\leq a_i\leq10^9)~.

Output Specification

On the first line, output a single integer, the maximum sum you can obtain.

On the second line, output the indices (~1~-indexed) of the prefix queries, in ascending order.

If there are multiple possible solutions, output the lexicographically least.

Subtasks

Subtask 1 (30%)

~N \leq 100~

Subtask 2 (70%)

No further constraints.

Sample Input 1

4
-1 2 3 4

Sample Output 1

10
1

Explanation for Sample 1

The maximum sum is ~10~, which can be obtained by flipping the signs of the elements up to the first element.

Sample Input 2

5
3 -4 -2 -9 10

Sample Output 2

28
1 4

Explanation for Sample 2

The original array is 3 -4 -2 -9 10.

The array, after the queries, is

3 -4 -2 -9 10
-3 -4 -2 -9 10
3 4 2 9 10

The maximum sum is ~28~.