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]
}

#[cfg(test)]
mod tests {

    use super::{p1, p2};

    #[test]
    fn test_p1() {
        assert_eq!(p1(5), 3);
    }

    #[test]
    fn test_p2() {
        assert_eq!(p2(5), 2);
    }
}

fn p2(n: usize) -> usize {
    let mut v1: VecDeque<usize> = (1..(n+1)/2 + 1).collect();
    let mut v2: VecDeque<usize> = ((n+1)/2 + 1..(n+1)).collect();
    loop {
        if v2.len() >= v1.len() {
            v2.pop_front();
            if v2.is_empty() {
                return v1[0];
            }
        } else {
            v1.pop_back();
        }
        v1.push_back(v2.pop_front().unwrap());
        v2.push_back(v1.pop_front().unwrap());
    }
}

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