const BOUND: i64 = 1_000_000_000_000;
const INF: i64 = BOUND * 200_000 + 1;

struct MaxCntSecond {
    max: i64,
    max_cnt: i64,
    second_max: i64,
}

impl MaxCntSecond {
    fn new(max: i64, max_cnt: i64, second_max: i64) -> Self {
        assert!(max_cnt > 0);
        assert!(max > second_max);
        MaxCntSecond {
            max: max,
            max_cnt: max_cnt,
            second_max: second_max,
        }
    }
    fn fold(&self, rhs: &Self) -> Self {
        match self.max.cmp(&rhs.max) {
            Ordering::Equal => MaxCntSecond::new(
                self.max,
                self.max_cnt + rhs.max_cnt,
                max(self.second_max, rhs.second_max),
            ),
            Ordering::Less => {
                MaxCntSecond::new(rhs.max, rhs.max_cnt, max(self.max, rhs.second_max))
            }
            Ordering::Greater => {
                MaxCntSecond::new(self.max, self.max_cnt, max(self.second_max, rhs.max))
            }
        }
    }
    fn tag(&self, val: i64) -> bool {
        self.second_max < val && val < self.max
    }
    fn chmin(&mut self, val: i64) -> i64 {
        assert!(self.tag(val));
        let diff = val - self.max;
        self.max = val;
        diff * self.max_cnt
    }
    fn add(&mut self, val: i64) {
        self.max += val;
        self.second_max += val;
    }
    fn update(&mut self, val: i64) {
        assert!(self.second_max < -BOUND);
        self.max = val;
        self.second_max = -INF;
    }
    fn parts(&self) -> (i64, i64, i64) {
        (self.max, self.max_cnt, self.second_max)
    }
}

struct MinCntSecond {
    min: i64,
    min_cnt: i64,
    second_min: i64,
}

impl MinCntSecond {
    fn new(min: i64, min_cnt: i64, second_min: i64) -> Self {
        assert!(min_cnt > 0);
        assert!(min < second_min);
        MinCntSecond {
            min: min,
            min_cnt: min_cnt,
            second_min: second_min,
        }
    }
    fn fold(&self, rhs: &Self) -> Self {
        match self.min.cmp(&rhs.min) {
            Ordering::Equal => MinCntSecond::new(
                self.min,
                self.min_cnt + rhs.min_cnt,
                min(self.second_min, rhs.second_min),
            ),
            Ordering::Greater => {
                MinCntSecond::new(rhs.min, rhs.min_cnt, min(self.min, rhs.second_min))
            }
            Ordering::Less => {
                MinCntSecond::new(self.min, self.min_cnt, min(self.second_min, rhs.min))
            }
        }
    }
    fn tag(&self, val: i64) -> bool {
        self.second_min > val && val > self.min
    }
    fn chmax(&mut self, val: i64) -> i64 {
        assert!(self.tag(val));
        let diff = val - self.min;
        self.min = val;
        diff * self.min_cnt
    }
    fn add(&mut self, val: i64) {
        self.min += val;
        self.second_min += val;
    }
    fn update(&mut self, val: i64) {
        assert!(self.second_min > BOUND);
        self.min = val;
        self.second_min = INF;
    }
    fn parts(&self) -> (i64, i64, i64) {
        (self.min, self.min_cnt, self.second_min)
    }
}

struct Value {
    max: MaxCntSecond,
    min: MinCntSecond,
    sum: i64,
    add: i64,
    len: i64,
}

impl Value {
    fn new(val: i64) -> Self {
        Value {
            max: MaxCntSecond::new(val, 1, -INF),
            min: MinCntSecond::new(val, 1,  INF),
            sum: val,
            add: 0,
            len: 1,
        }
    }
    fn get_sum(&self) -> i64 {
        self.sum
    }
    fn get_max(&self) -> i64 {
        self.max.max
    }
    fn get_min(&self) -> i64 {
        self.min.min
    }
    fn fold(&self, rhs: &Self) -> Self {
        let max = self.max.fold(&rhs.max);
        let min = self.min.fold(&rhs.min);
        assert!(max.max >= min.min);
        let sum = self.get_sum() + rhs.get_sum();
        let len = self.len + rhs.len;
        Value {
            max: max,
            min: min,
            sum: sum,
            add: 0,
            len: len,
        }
    }
    fn tag_max(&self, val: i64) -> bool {
        self.max.tag(val)
    }
    fn tag_min(&self, val: i64) -> bool {
        self.min.tag(val)
    }
    fn chmin(&mut self, x: i64) {
        assert!(self.tag_max(x));
        let (a, _, _) = self.max.parts();
        let (p, _, r) = self.min.parts();
        self.sum += self.max.chmin(x);
        if a == p {
            self.min.update(x);
        } else if r == a {
            self.min.second_min = x;
        }
    }
    fn chmax(&mut self, x: i64) {
        assert!(self.tag_min(x));
        let (a, _, _) = self.max.parts();
        let (p, _, r) = self.min.parts();
        self.sum += self.min.chmax(x);
        if a == p {
            self.max.update(x);
        } else if r == a {
            self.max.second_max = x;
        }
    }
    fn add(&mut self, val: i64) {
        self.max.add(val);
        self.min.add(val);
        self.sum += val * self.len;
        self.add += val;
    }
}

fn propagate(seg: &mut [Value], k: usize) {
    let v = seg[k].add;
    seg[k].add = 0;
    let max = seg[k].get_max();
    let min = seg[k].get_min();
    for s in seg[(2 * k)..].iter_mut().take(2) {
        s.add(v);
        if s.tag_max(max) {
            s.chmin(max);
        }
        if s.tag_min(min) {
            s.chmax(min);
        }
    }
}

fn update(seg: &mut [Value], k: usize) {
    assert!(seg[k].add == 0);
    seg[k] = seg[2 * k].fold(&seg[2 * k + 1]);
}

fn update_chmin(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {
    if y <= l || r <= x || seg[k].get_max() <= val {
        return;
    }
    if x <= l && r <= y && seg[k].tag_max(val) {
        seg[k].chmin(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_chmin(seg, 2 * k, l, m, x, y, val);
    update_chmin(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn update_chmax(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {
    if y <= l || r <= x || seg[k].get_min() >= val {
        return;
    }
    if x <= l && r <= y && seg[k].tag_min(val) {
        seg[k].chmax(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_chmax(seg, 2 * k, l, m, x, y, val);
    update_chmax(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn update_add(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {
    if y <= l || r <= x {
        return;
    }
    if x <= l && r <= y {
        seg[k].add(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_add(seg, 2 * k, l, m, x, y, val);
    update_add(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn find_sum(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> i64 {
    if y <= l || r <= x {
        return 0;
    }
    if x <= l && r <= y {
        return seg[k].get_sum();
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    find_sum(seg, 2 * k, l, m, x, y) + find_sum(seg, 2 * k + 1, m, r, x, y)
}

use proconio::*;
use proconio::marker::*;
use std::collections::*;
use std::cmp::*;
use std::ops::Bound::*;

#[fastout]
fn run() {
    input! {
        n: usize,
        q: usize,
        ask: [(u8, usize); q],
    }
    let size = (n + 2).next_power_of_two();
    let mut row: Vec<_> = (0..(2 * size)).map(|_| Value::new(0)).collect();
    for s in row[size..].iter_mut().skip(2).take(n - 2) {
        let v = (n - 2) as i64;
        *s = Value::new(v);
    }
    for i in (1..size).rev() {
        update(&mut row, i);
    }
    let mut col: Vec<_> = (0..(2 * size)).map(|_| Value::new(0)).collect();
    for s in col[size..].iter_mut().skip(2).take(n - 2) {
        let v = (n - 2) as i64;
        *s = Value::new(v);
    }
    for i in (1..size).rev() {
        update(&mut col, i);
    }
    let mut ans = ((n - 2) as i64).pow(2);
    for (op, x) in ask {
        if op == 1 {
            let k = find_sum(&mut row, 1, 0, size, x, x + 1);
            ans -= k;
            update_chmin(&mut row, 1, 0, size, x, x + 1, 0);
            update_chmin(&mut col, 1, 0, size, 0, 3 + k as usize,  x as i64 - 2);
        } else {
            let k = find_sum(&mut col, 1, 0, size, x, x + 1);
            ans -= k;
            update_chmin(&mut col, 1, 0, size, x, x + 1, 0);
            update_chmin(&mut row, 1, 0, size, 0, 3 + k as usize, x as i64 - 2);
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 80672