You are given N coins arranged in a row. Each coin has a positive value. Select a subset of coins to maximize the total value, with the constraint that no two selected coins can be adjacent.

Input Format

• First line: integer ~N~ ~(1 ≤ N ≤ 10^6)~
• Second line: ~N~ positive integers ~v_i~ ~(1 ≤ v_i ≤ 10^6)~

Output Format

• First line: Maximum total value
• Second line: Indices of selected coins in any order (1-indexed)

Example Input

4
5 1 3 2

Example Output

8
1 3