AtCoder Beginner Contest 443 D

https://atcoder.jp/contests/abc443/tasks/abc443_d

まず一番上から考えて、その隣を上げることにします。隣が自分より2以上低ければそこを1低いところまで上げます。その隣は考えてはいけません。例えば、1 2 4 1となっていたら、2はそのままでよくて、4を3に上げますが、その右が1なので、結局2にしないといけないのでムダです。なので、上げたらそこの値は更新して次に備えます。そして、さっき一番上だったものを除いて一番上を同様に処理し、なくなるまで続けます。

// Pawn Line
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_case() -> Vec<i32> {
    let _N: usize = read();
    let R: Vec<i32> = read_vec();
    R
}

use std::collections::BTreeSet;

fn F_each(mut R: Vec<i32>) -> i64 {
    let N = R.len();
    let mut set: BTreeSet<(i32, usize)> = R.iter().enumerate().
                                            map(|(i, &e)| (e, i)).collect();
    let mut n: i64 = 0;
    while let Some(&(_, i)) = set.iter().next() {
        set.remove(&(R[i], i));
        if i > 0 {
            // 左を見る
            if R[i-1] > R[i] + 1 {
                set.remove(&(R[i-1], i-1));
                n += (R[i-1] - R[i] - 1) as i64;
                R[i-1] = R[i] + 1;
                set.insert((R[i-1], i-1));
            }
        }
        if i < N - 1 {
            // 右を見る
            if R[i+1] > R[i] + 1 {
                set.remove(&(R[i+1], i+1));
                n += (R[i+1] - R[i] - 1) as i64;
                R[i+1] = R[i] + 1;
                set.insert((R[i+1], i+1));
            }
        }
    }
    n
}

fn F(T: usize) {
    for _ in 0..T {
        let R = read_case();
        println!("{}", F_each(R))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}