// codesnip-guard: CartesianTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::cartesian_tree::CartesianTree;#[cfg_attr(any(),rustfmt::skip)]mod cartesian_tree{use std::ops::Range;#[derive(Debug,Clone)]pub struct CartesianTree{pub root:usize,pub parents:Vec<usize>,pub children:Vec<[usize;2]>}impl CartesianTree{pub fn new<T>(a:&[T])->Self where T:PartialOrd{let mut parents=vec![!0;a.len()];let mut children=vec![[!0;2];a.len()];let mut root=!0;for i in 0..a.len(){let mut prev=!0;let mut parent=i.wrapping_sub(1);while parent!=!0&&a[i]<a[parent]{prev=parent;parent=parents[parent];}parents[i]=parent;if parent!=!0{children[parent][1]=i;}else{root=i;}if prev!=!0{parents[prev]=i;children[i][0]=prev;}}Self{root,parents,children}}pub fn with_ranges(&self,mut f:impl FnMut(usize,Range<usize>)){let mut stack=vec![(self.root,0,self.parents.len())];while let Some((v,l,r))=stack.pop(){f(v,l..r);if self.children[v][1]!=!0{stack.push((self.children[v][1],v+1,r));}if self.children[v][0]!=!0{stack.push((self.children[v][0],l,v));}}}}}