macro_rules !read_value {($iter :expr ,($($t :tt ) ,*) ) =>{($(read_value !($iter ,$t ) ) ,*) } ;($iter :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($iter ,$t ) ) .collect ::<Vec <_ >>() } ;($iter :expr ,{chars :$base :expr } ) =>{read_value !($iter ,String ) .chars () .map (|c |(c as u8 -$base as u8 ) as usize ) .collect ::<Vec <usize >>() } ;($iter :expr ,{char :$base :expr } ) =>{read_value !($iter ,{chars :$base } ) [0 ] } ;($iter :expr ,chars ) =>{read_value !($iter ,String ) .chars () .collect ::<Vec <char >>() } ;($iter :expr ,char ) =>{read_value !($iter ,chars ) [0 ] } ;($iter :expr ,usize1 ) =>{read_value !($iter ,usize ) -1 } ;($iter :expr ,$t :ty ) =>{$iter .next () .unwrap () .parse ::<$t >() .unwrap () } ;}
macro_rules !input_inner {($iter :expr ) =>{} ;($iter :expr ,) =>{} ;($iter :expr ,mut $var :ident :$t :tt $($r :tt ) *) =>{let mut $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,mut $var :ident $($r :tt ) *) =>{input_inner !{$iter ,mut $var :usize $($r ) *} } ;($iter :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,$var :ident $($r :tt ) *) =>{input_inner !{$iter ,$var :usize $($r ) *} } ;}
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;(iter =$iter :ident ,$($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut $iter =s .split_whitespace () ;input_inner !{$iter ,$($r ) *} } ;($($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut iter =s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;}
fn main() {
    input! { n, a: [i64; n] };
    if a.iter().filter(|&&aa| aa >= 0).count() <= 1 {
        let i = (0..n).max_by_key(|&i| a[i]).unwrap();
        println!("{}", a[i]);
        println!("{}", n - 1);
        for j in (i + 2..n + 1).rev() {
            println!("{}", j);
        }
        for _j in 0..i {
            println!("{}", 1);
        }
        return;
    }
    let mut odd = vec![false; n];
    let mut oddsum = 0;
    let mut even = vec![false; n];
    let mut evensum = 0;
    for i in 0..n {
        if a[i] >= 0 {
            if i % 2 == 1 {
                odd[i] = true;
                oddsum += a[i];
            } else {
                even[i] = true;
                evensum += a[i];
            }
        }
    }
    let mut p = vec![];
    let z = if oddsum > evensum {
        println!("{}", oddsum);
        odd
    } else {
        println!("{}", evensum);
        even
    };
    let mut i = n - 1;
    while !z[i] {
        p.push(i + 1);
        i -= 1;
    }
    while i > 0 {
        let mut j = i - 1;
        while !z[j] {
            if j == 0 {
                break;
            }
            j -= 1;
        }
        if z[j] {
            let l = i - j;
            for k in (j + 1..j + l / 2 + 1).rev() {
                p.push(k + 1);
            }
        } else {
            for _k in 0..i {
                p.push(1);
            }
        }
        i = j;
    }

    println!("{}", p.len());
    for x in p.into_iter() {
        println!("{}", x);
    }
}


Measured memory_bytes: 4352