Järjestäminen

use std::io::{self, BufRead};

fn main() {
    let mut lines = io::BufReader::new(io::stdin()).lines();

    let t = lines.next().unwrap().unwrap().parse::<usize>().unwrap();

    let mut arrays: Vec<Vec<usize>> = Vec::new();

    for _ in 0..t {
        let _n = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
        let array_line = lines.next().unwrap().unwrap();
        arrays.push(array_line.split_ascii_whitespace().map(|s| s.parse::<usize>().unwrap()).collect());
    }

    for array in &mut arrays {
        if try_sort(1, array) {
            println!("YES");
        } else {
            println!("NO");
        }
    }
}

fn try_sort(m: usize, array: &mut [usize]) -> bool {
    if array.len() == 1 {
        return true
    }
    if array.len() == 2 {
        return array[0] < array[1]
    }
    if array.len() == 3 {
        return array[0] < array[1] && array[1] < array[2]
    }

    if Some(&m) == array.iter().nth(1) {
        return false;
    }

    if Some(&m) == array.last() {
        let i = array.len() - 2;

        let tmp1 = array[0];
        let tmp2 = array[1];

        array[0] = array[i];
        array[1] = array[i+1];
        
        array[i] = tmp1;
        array[i+1] = tmp2;

        return try_sort(m, array);
    }

    if m == array[0] {
        return try_sort(m + 1, &mut array[1..])
    } else {
        let i = array.iter().position(|x| *x == m).unwrap();

        let tmp1 = array[0];
        let tmp2 = array[1];

        array[0] = array[i];
        array[1] = array[i+1];
        
        array[i] = tmp1;
        array[i+1] = tmp2;

        return try_sort(m + 1, &mut array[1..])
    }
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER