use proconio::input; fn main() { input! { n:usize, mut r:[(usize,usize);n], } r.sort(); let mut indegs = vec![0; n]; let mut sorted_idx = (0..n).collect::>(); sorted_idx.sort_by(|i, j| r[*j].1.cmp(&r[*i].1)); for i in sorted_idx { let id = r.lower_bound((r[i].1, 0)); if id >= n || indegs[id] > 0 { continue; } indegs[id] += 1; } let ans = indegs.iter().filter(|indeg| **indeg == 0).count() - 1; println!("{}", ans); } use bound::*; mod bound { pub trait Bound { fn lower_bound(&self, val: T) -> usize; fn upper_bound(&self, val: T) -> usize; } impl Bound for [T] where T: Ord + Copy, { fn lower_bound(&self, val: T) -> usize { let mut ok = self.len(); let mut ng = !0; while ok.wrapping_sub(ng) > 1 { let m = ok.wrapping_add(ng) / 2; if val <= self[m] { ok = m; } else { ng = m; } } ok } fn upper_bound(&self, val: T) -> usize { let mut ok = !0; let mut ng = self.len(); while ng.wrapping_sub(ok) > 1 { let m = ng.wrapping_add(ok) / 2; if self[m] <= val { ok = m; } else { ng = m; } } ok } } }