// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] // use core::num; use std::cmp::*; use std::fmt::*; use std::hash::*; use std::iter::FromIterator; use std::*; use std::{cmp, collections, fmt, io, iter, ops, str}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const LINF: i64 = 2147483647; const INF128: i128 = 1223372036854775807000000000000; const MOD1: i64 = 1000000007; const MOD9: i64 = 998244353; const MOD: i64 = MOD9; // const MOD: i64 = MOD2; const UMOD: usize = MOD as usize; const M_PI: f64 = 3.14159265358979323846; // use proconio::input; // const MOD: i64 = INF; use cmp::Ordering::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { //if expr println!("{}", $x); }; } macro_rules! vp { // vector print separate with space ($x:expr) => { println!( "{}", $x.iter() .map(|x| x.to_string()) .collect::>() .join(" ") ); }; } macro_rules! d { ($x:expr) => { eprintln!("{:?}", $x); }; } macro_rules! yn { ($val:expr) => { if $val { println!("Yes"); } else { println!("No"); } }; } macro_rules! map{ // declear btreemap ($($key:expr => $val:expr),*) => { { let mut map = ::std::collections::BTreeMap::new(); $( map.insert($key, $val); )* map } }; } macro_rules! set{ // declear btreemap ($($key:expr),*) => { { let mut set = ::std::collections::BTreeSet::new(); $( set.insert($key); )* set } }; } fn main() { solve(); } // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readff() -> (f64, f64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readcc() -> (char, char) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readuuu() -> (usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readiiii() -> (i64, i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } fn read_imat(h: usize) -> Vec> { (0..h).map(|_| read_vec()).collect() } fn read_cmat(h: usize) -> Vec> { (0..h).map(|_| read::().chars().collect()).collect() } pub struct Dsu { n: usize, // root node: -1 * component size // otherwise: parent parent_or_size: Vec, } impl Dsu { // 0 <= size <= 10^8 is constrained. pub fn new(size: usize) -> Self { Self { n: size, parent_or_size: vec![-1; size], } } pub fn merge(&mut self, a: usize, b: usize) -> usize { assert!(a < self.n); assert!(b < self.n); let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if -self.parent_or_size[x] < -self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] += self.parent_or_size[y]; self.parent_or_size[y] = x as i32; x } pub fn same(&mut self, a: usize, b: usize) -> bool { assert!(a < self.n); assert!(b < self.n); self.leader(a) == self.leader(b) } pub fn leader(&mut self, a: usize) -> usize { assert!(a < self.n); if self.parent_or_size[a] < 0 { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32; self.parent_or_size[a] as usize } pub fn size(&mut self, a: usize) -> usize { assert!(a < self.n); let x = self.leader(a); -self.parent_or_size[x] as usize } pub fn groups(&mut self) -> Vec> { let mut leader_buf = vec![0; self.n]; let mut group_size = vec![0; self.n]; for i in 0..self.n { leader_buf[i] = self.leader(i); group_size[leader_buf[i]] += 1; } let mut result = vec![Vec::new(); self.n]; for i in 0..self.n { result[i].reserve(group_size[i]); } for i in 0..self.n { result[leader_buf[i]].push(i); } result .into_iter() .filter(|x| !x.is_empty()) .collect::>>() } } pub struct SEG { n: usize, buf: Vec, } impl SEG { #[allow(dead_code)] pub fn new(n: usize) -> SEG { SEG { n, buf: vec![M::id(); 2 * n], } } #[allow(dead_code)] pub fn update(&mut self, k: usize, a: M::T) { let mut k = k + self.n; self.buf[k] = a; while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn add(&mut self, k: usize, a: &M::T) { let mut k = k + self.n; self.buf[k] = M::op(&self.buf[k], a); while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn get(&self, i: usize) -> M::T { self.query(i, i + 1) } #[allow(dead_code)] pub fn query_range>(&self, range: R) -> M::T { let l = match range.start_bound() { std::ops::Bound::Excluded(&x) => { assert!(x > 0); x - 1 } std::ops::Bound::Included(&x) => x, std::ops::Bound::Unbounded => 0, }; let r = match range.end_bound() { std::ops::Bound::Excluded(&x) => x, std::ops::Bound::Included(&x) => (x + 1), std::ops::Bound::Unbounded => self.n, }; self.query(l, r) } #[allow(dead_code)] pub fn query(&self, l: usize, r: usize) -> M::T { let mut vl = M::id(); let mut vr = M::id(); let mut l = l + self.n; let mut r = r + self.n; while l < r { if l & 1 == 1 { vl = M::op(&vl, &self.buf[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = M::op(&self.buf[r], &vr); } l >>= 1; r >>= 1; } M::op(&vl, &vr) } } pub trait Monoid { type T: Clone; fn id() -> Self::T; fn op(a: &Self::T, b: &Self::T) -> Self::T; } pub enum MON {} impl Monoid for MON { type T = u64; fn id() -> Self::T { 0 } fn op(a: &Self::T, b: &Self::T) -> Self::T { *a + *b } } fn solve() { let n: usize = read(); let mut data1 = vec![]; let mut data2 = vec![]; for i in 0..n { let (a, b) = readuu(); data1.push((a, b)); data2.push((b, a)); } let mut m1 = 0; let mut m2 = UINF; data1.sort(); data2.sort(); data2.reverse(); for i in 0..n { let x = i + 1; if x + m1 < data1[i].0 { m1 = max(m1, data1[i].0 - x); } if x + m1 > data1[i].1 { p!(0); return; } } for i in 0..n { let x = n - i; if x + m2 > data2[i].0 { // dbg!(x, m2, data2[i].0); m2 = min(m2, data2[i].0 - x); } if x + m2 < data2[i].1 { p!(0); return; } } p!(max(0, m2 as i64 - m1 as i64 + 1)); return; }