You are given ~N~ coins arranged in a row. Each coin has a positive value. Your goal is to select a subset of coins such that:

1. No two selected coins are adjacent in the row.
2. The total value of the selected coins is maximized.

Output the indices of all valid optimal solutions, or up to ~100~ of them if there are more.

Input Format

The first line contains a single integer ~N~:

• ~N~ ~(1 ≤ N ≤ 10^6)~: the number of coins

The second line contains ~N~ positive integers:

• ~v_1, v_2, ..., v_N~ ~(1 ≤ v_i ≤ 10^6)~: the values of the coins

Output Format

• The first line contains a single integer: the maximum total value that can be achieved.
• Each subsequent line contains the indices of one valid optimal solution, separated by spaces.
• You may output up to ~100~ different optimal solutions.
• Coins are numbered from ~1~ to ~N~.

Example

Input

4
5 5 5 5

Output

10
1 3
1 4
2 4

Notes

• No two printed indices in the same solution may be adjacent.
• If multiple optimal solutions exist, you may output all of them, or any subset of up to ~100~ optimal solutions.
• The order of indices within each line does not matter.
• Each printed line after the first must represent a distinct valid optimal solution.

Constraints

• Time limit: 1 second
• Memory limit: 1GB
• ~1 ≤ N ≤ 10^6~
• ~1 ≤ v_i ≤ 10^6~