#[allow(unused_imports)]
use {
    itertools::Itertools,
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::io::Write,
    std::ops::*,
};

#[allow(unused_macros)]
macro_rules! dbg { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; }

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        query: [(usize, Usize1); q]
    }
    let mut sx = SegmentTree::<Node>::new(n);
    let mut sy = SegmentTree::<Node>::new(n);
    for i in 1..n - 1 {
        sx.update(i, n - 1);
        sy.update(i, n - 1);
    }
    let mut ans = (n - 2) * (n - 2);
    for (t, x) in query {
        if t == 1 {
            let k = sy.prod(x..);
            ans -= k - 1;
            let y = sx.get(k - 1);
            sx.update(k - 1, min(x, y));
        } else {
            let k = sx.prod(x..);
            ans -= k - 1;
            let y = sy.get(k - 1);
            sy.update(k - 1, min(x, y));
        }
    }
    println!("{}", ans);
}

struct Node;
impl Monoid for Node {
    type T = usize;
    fn id() -> Self::T {
        10000000
    }
    fn f(a: &Self::T, b: &Self::T) -> Self::T {
        min(*a, *b)
    }
}
trait Monoid {
    type T: Clone;
    fn id() -> Self::T;
    fn f(a: &Self::T, b: &Self::T) -> Self::T;
}
struct SegmentTree<M: Monoid> {
    width: usize,
    node: Vec<M::T>,
}
#[allow(dead_code)]
impl<M: Monoid> SegmentTree<M> {
    fn new(n: usize) -> Self {
        let width = n.next_power_of_two();
        Self {
            width,
            node: vec![M::id(); width << 1],
        }
    }
    fn from_vec(a: &[M::T]) -> Self {
        let width = a.len().next_power_of_two();
        let mut node = vec![M::id(); width << 1];
        for i in 0..a.len() {
            node[i + width] = a[i].clone();
        }
        for i in (1..width).rev() {
            node[i] = M::f(&node[i << 1], &node[1 + (i << 1)]);
        }
        Self { width, node }
    }
    fn update(&mut self, idx: usize, v: M::T) {
        let mut now = idx + self.width;
        self.node[now] = v;
        now = now >> 1;
        while now > 0 {
            self.node[now] = M::f(&self.node[now << 1], &self.node[1 + (now << 1)]);
            now = now >> 1;
        }
    }
    fn get(&self, idx: usize) -> M::T {
        self.node[idx + self.width].clone()
    }
    fn prod<R>(&self, range: R) -> M::T
    where
        R: std::ops::RangeBounds<usize>,
    {
        let mut l = match range.start_bound() {
            std::ops::Bound::Included(&a) => a,
            _ => 0,
        } + self.width;
        let mut r = match range.end_bound() {
            std::ops::Bound::Excluded(&a) => a,
            std::ops::Bound::Included(&a) => a + 1,
            _ => self.width,
        } + self.width;
        let mut x = M::id();
        let mut y = M::id();
        while l < r {
            if l & 1 == 1 {
                x = M::f(&x, &self.node[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = M::f(&self.node[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        M::f(&x, &y)
    }
}


Measured memory_bytes: 14916