use input::input_array; use input::input_vec; use std::cmp::Ordering; use std::collections::BTreeSet; use std::ops::Bound; fn main() { let [n, _m] = input_array::(); let mut a = input_vec::(); for x in &mut a { *x -= 1; } let mut dist = Dist { table: (0..n).collect(), set: BTreeSet::from_iter(vec![0, n - 1]), }; for &x1 in a.iter().rev() { let x2 = x1 + 1; if x1 != 0 { dist.at(x1 - 1); } let y1 = *dist.at(x1); let y2 = *dist.at(x2); if x2 != n - 1 { dist.at(x2 + 1); } match y1.cmp(&y2) { Ordering::Equal => {} Ordering::Less => { if x1 == 0 || *dist.at(x1 - 1) >= *dist.at(x1) { *dist.at(x1) += 1; } let x3 = dist .set .range(x2..) .copied() .take_while(|&x3| dist.table[x3] == y2 + x3 - x2) .last() .unwrap(); if x2 != x3 { while let Some(x) = dist .set .range((Bound::Excluded(x2), Bound::Excluded(x3))) .copied() .next() { dist.set.remove(&x); } if x3 + 1 < n { dist.at(x3 + 1); } *dist.at(x3) -= 1; } *dist.at(x2) -= 1; } Ordering::Greater => { if x2 == n - 1 || *dist.at(x2 + 1) >= *dist.at(x2) { *dist.at(x2) += 1; } let x0 = dist .set .range(..=x1) .rev() .copied() .take_while(|&x0| dist.table[x0] == y1 + x1 - x0) .last() .unwrap(); if x0 != x1 { while let Some(x) = dist .set .range((Bound::Excluded(x0), Bound::Excluded(x1))) .copied() .next() { dist.set.remove(&x); } if x0 != 0 { dist.at(x0 - 1); } *dist.at(x0) -= 1; } *dist.at(x1) -= 1; } } } println!( "{}", (1..n) .map(|i| *dist.at(i)) .map(|x| x.to_string()) .collect::>() .join(" ") ); } #[derive(Debug)] struct Dist { table: Vec, set: BTreeSet, } impl Dist { fn at(&mut self, x: usize) -> &mut usize { let x0 = self.set.range(..=x).next_back().unwrap(); let x1 = self.set.range(x..).next().unwrap(); let y0 = self.table[*x0]; let y1 = self.table[*x1]; assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0); let y = y0 + x - x0; self.table[x] = y; self.set.insert(x); &mut self.table[x] } } // input {{{ #[allow(dead_code)] mod input { use std::cell::Cell; use std::convert::TryFrom; use std::io::stdin; use std::io::BufRead; use std::io::BufReader; use std::io::Lines; use std::io::Stdin; use std::str::FromStr; use std::sync::Mutex; use std::sync::Once; type Server = Mutex>>; static ONCE: Once = Once::new(); pub struct Lazy(Cell>); unsafe impl Sync for Lazy {} fn line() -> String { static SYNCER: Lazy = Lazy(Cell::new(None)); ONCE.call_once(|| { SYNCER .0 .set(Some(Mutex::new(BufReader::new(stdin()).lines()))); }); unsafe { (*SYNCER.0.as_ptr()) .as_ref() .unwrap() .lock() .unwrap() .next() .unwrap() .unwrap() } } pub trait ForceFromStr: FromStr { fn force_from_str(s: &str) -> Self; } impl ForceFromStr for T where T: FromStr, E: std::fmt::Debug, { fn force_from_str(s: &str) -> Self { s.parse().unwrap() } } pub fn input_array() -> [T; N] where T: std::fmt::Debug, { <[_; N]>::try_from(input_vec()).unwrap() } pub fn input_vec() -> Vec { line() .split_whitespace() .map(T::force_from_str) .collect::>() } pub fn input() -> T { T::force_from_str(&line()) } } // }}} // lg {{{ #[allow(dead_code)] mod lg { use std::borrow::Borrow; use std::fmt; use std::iter::once; #[macro_export] macro_rules! lg { (@contents $head:expr $(, $tail:expr)*) => {{ $crate::__lg_internal!($head); $( eprint!(","); $crate::__lg_internal!($tail); )* eprintln!(); }}; ($($expr:expr),* $(,)?) => {{ eprint!("{}笶ッ", line!()); $crate::lg!(@contents $($expr),*) }}; } #[doc(hidden)] #[macro_export] macro_rules! __lg_internal { ($value:expr) => {{ match $value { head => { eprint!( " {} = {}", stringify!($value), $crate::lg::__quiet(format!("{:?}", &head)) ); } } }}; } #[macro_export] macro_rules! rows { { $index_label:literal, $(@offset $offset:expr,)? $(@verticalbar $verticalbar:expr,)* $($(@$label:literal =>)? $values:expr),* $(,)? } => {{ #![allow(unused_assignments)] let mut rows = $crate::lg::Rows::default(); rows.line_number(line!()); $(rows.offset($offset);)? $(rows.verticalbar($verticalbar);)* rows.index_label($index_label); $({ let mut label = stringify!($values).to_string(); if label.starts_with("&") { label = label[1..].to_string(); } $({ let label_: &'static str = $label; label = label_.to_string(); })? rows.row(label, $values); })* eprintln!("{}", rows.to_string_table()); }}; } #[macro_export] macro_rules! table { { $(@$name:literal => )? $values:expr $(,)? } => {{ #![allow(unused_assignments)] let mut name = stringify!($values).to_string(); if name.starts_with("&") { name = name[1..].to_string(); } $({ let name_: &'static str = $name; name = name_.to_string(); })? let mut rows = $crate::lg::Rows::default(); rows.line_number(line!()); rows.table_name(name); #[allow(array_into_iter)] for (i, row) in $values.into_iter().enumerate() { rows.row(i.to_string(), row); } eprintln!("{}", rows.to_string_table()); }}; } #[doc(hidden)] pub fn __quiet(s: impl AsRef) -> String { s.as_ref() .replace("340282366920938463463374607431768211455", "*") // u128 .replace("170141183460469231731687303715884105727", "*") // i128 .replace("18446744073709551615", "*") // u64 .replace("9223372036854775807", "*") // i64 .replace("-9223372036854775808", "*") // i64 .replace("4294967295", "*") // u32 .replace("2147483647", "*") // i32 .replace("-2147483648", "*") // i32 .replace("None", "*") .replace("Some", "") .replace("true", "#") .replace("false", ".") .replace(['"', '\''], "") } #[doc(hidden)] #[derive(Default)] pub struct Rows { line_number: String, index_label: String, offset: usize, verticalbars: Vec, table_name: String, rows: Vec, } impl Rows { pub fn line_number(&mut self, line_number: u32) -> &mut Self { self.line_number = format!("{}", line_number); self } pub fn index_label(&mut self, index_label: impl Into) -> &mut Self { self.index_label = index_label.into(); self } pub fn offset(&mut self, offset: usize) -> &mut Self { self.offset = offset; self } pub fn verticalbar(&mut self, verticalbar: impl IntoIterator) -> &mut Self { self.verticalbars.extend(verticalbar); self } pub fn table_name(&mut self, table_name: impl Into) -> &mut Self { self.table_name = table_name.into(); self } pub fn row( &mut self, label: impl Into, values: impl IntoIterator, ) -> &mut Self { self.rows.push(Row { label: label.into(), values: values .into_iter() .map(|value| __quiet(format!("{:?}", value))) .collect(), }); self } pub fn to_string_table(self) -> StringTable { let Self { line_number, index_label, offset, verticalbars, table_name, rows, } = self; let w = rows .iter() .map(|row| row.values.len()) .max() .unwrap_or_default(); let mut verticalbar_count = vec![0; w + 1]; for &v in &verticalbars { if (offset..=offset + w).contains(&v) { verticalbar_count[v - offset] += 1; } } StringTable { head: StringRow { label: format!( "{line_number}笶ッ {table_name}{index_label}", index_label = if index_label.is_empty() { String::new() } else { format!("[{}]", index_label) } ), values: (offset..offset + w) .map(|index| index.to_string()) .collect(), }, body: rows .iter() .map(|row| StringRow { label: row.label.clone(), values: row.values.clone(), }) .collect(), verticalbar_count, } } } struct Row { label: String, values: Vec, } #[doc(hidden)] pub struct StringTable { head: StringRow, body: Vec, verticalbar_count: Vec, } impl fmt::Display for StringTable { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let Self { head, body, verticalbar_count, } = self; let w = body .iter() .map(|row| row.values.len()) .max() .unwrap_or_default(); let label_width = once(head.label.chars().count()) .chain(body.iter().map(|row| row.label.chars().count())) .max() .unwrap(); let value_width = (0..w) .map(|j| { once(j.to_string().len()) .chain( body.iter() .map(|row| row.values.get(j).map_or(0, |s| s.chars().count())), ) .max() .unwrap() }) .collect::>(); // Heading gray(f)?; write!( f, "{}", head.to_string(label_width, &value_width, verticalbar_count, true) )?; resetln(f)?; // Body for row in body { write!( f, "{}", row.to_string(label_width, &value_width, verticalbar_count, false) )?; writeln!(f)?; } Ok(()) } } struct StringRow { label: String, values: Vec, } impl StringRow { fn to_string( &self, label_width: usize, value_width: &[usize], varticalbars_count: &[usize], label_align_left: bool, ) -> String { let Self { label, values } = self; let w = value_width.len(); let mut s = String::new(); s.push_str(&if label_align_left { format!("{label: { s.push_str(&format!(" {value:>value_width$}",)); } None => { s.push_str(" ".repeat(value_width + 1).as_str()); } } } s } } const GRAY: &str = "\x1b[48;2;127;127;127;37m"; const RESET: &str = "\x1b[0m"; fn gray(f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{GRAY}") } fn resetln(f: &mut fmt::Formatter<'_>) -> fmt::Result { writeln!(f, "{RESET}") } pub fn bools(iter: I) -> String where B: Borrow, I: IntoIterator, { format!( "[{}]", iter.into_iter() .map(|b| ['.', '#'][usize::from(*(b.borrow()))]) .collect::(), ) } } // }}}