extern crate itertools;

use itertools::Itertools;
use std::collections::VecDeque;

fn p1(n: usize) -> usize {
    let mut v: VecDeque<usize> = (1..n + 1).collect();
    while v.len() > 1 {
        let front = v.pop_front().unwrap();
        v.push_back(front);
        v.pop_front();
    }
    v[0]
}

fn step_p2(v: Vec<usize>) -> Vec<usize> {
    let mut r = Vec::with_capacity(v.len() * 8 / 9);
    let first_high = (v.len() + 2) / 3;
    let after_last_high = v.len() / 2;
    let first_inc = 2 - v.len() % 2;
    for &e in v[first_high..after_last_high].iter() {
        r.push(e);
    }
    for i in (after_last_high + first_inc..v.len()).step(3) {
        r.push(v[i]);
    }
    for &e in v[..first_high].iter() {
        r.push(e);
    }
    r
}

fn p2(n: usize) -> usize {
    let mut v: Vec<usize> = (1..(n + 1)).collect();
    while v.len() > 1 {
        v = step_p2(v);
    }
    v[0]
}

fn main() {
    const INPUT: usize = 3012210;
    println!("P1 = {}", p1(INPUT));
    println!("P2 = {}", p2(INPUT));
}