Key cutting

use std::str::FromStr;
use std::fmt::Debug;
 
fn read<T: FromStr>() -> Vec<T> where <T as FromStr>::Err: Debug  {
    let stdin = std::io::stdin();
    let line = stdin.lines().next().unwrap().unwrap();
    line.split_whitespace().map(T::from_str).map(|x| x.unwrap()).collect()
}
 
fn main() {
    let _n = read::<usize>()[0];
    let mut hs = read::<u32>();
 
    hs.dedup();
 
    let mut ll = hs.iter().enumerate().map(|(i, h)| (*h, i.wrapping_sub(1), i + 1, true)).collect::<Vec<_>>();
 
    let mut steps = 0;
 
    let mut q = hs.into_iter().enumerate().collect::<Vec<_>>();
    q.sort_by_key(|(_i, h)| *h);
 
    while let Some((i, h)) = q.pop() {
        if h == 0 {
            break;
        }
 
        let (_h, p, n, a) = ll[i];
        if a {
            ll[i].3 = false;
            steps += 1;
            let Some((hp, _pp, _np, _)) = ll.get(p) else {
                if ll.get(n).is_some() {
                    ll[n].1 = usize::MAX;
                }
                continue;
            };
 
            let Some((hn, _pn, _nn, _)) = ll.get(n) else {
                if ll.get(p).is_some() {
                    ll[p].2 = usize::MAX;
                }
                continue;
            };
 
            if hp == hn {
                ll[n].3 = false;
                let nn = ll[n].2;
                if ll.get(nn).is_some() {
                    ll[p].2 = nn;
                    ll[nn].1 = p;
                } else {
                    ll[p].2 = usize::MAX;
                }
            } else {
                ll[p].2 = n;
                ll[n].1 = p;
            }
 
        }
    }
 
    println!("{steps}");
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED