#![allow(non_snake_case)] use ac_library::segtree::{Additive, Segtree}; use proconio::*; // https://maguro.dev/blog/debug-macro/ #[allow(unused_macros)] macro_rules! debug { ($($a:expr),* $(,)*) => { #[cfg(debug_assertions)] eprintln!(concat!($("| ", stringify!($a), " = {:?} "),*, "|"), $(&$a),*); }; } fn main() { std::thread::Builder::new() .stack_size(256 * 1024 * 1024) .spawn(solve) .unwrap() .join() .unwrap(); } // K 個飛ばしで sort する // swap 回数は転倒数 // sort して 全体が sort されてれば OK fn solve() { input! { n: usize, k: usize, p: [usize; n] } let mut sorted = vec![0; n]; let mut res = 0; for s in 0..k { let mut v = vec![]; let mut st = Segtree::>::from_iter(std::iter::repeat(0).take(n + 1)); for i in (0..).take_while(|&u| s + u * k < n) { let x = p[s + i * k]; res += st.prod(0..=x); st.set(x, 1); v.push(x); } v.sort(); for i in 0..v.len() { sorted[s + k * i] = v[i]; } } if sorted.is_sorted() { println!("{res}"); } else { println!("-1") } }