module segment_tree_mod
    use,intrinsic :: iso_fortran_env
    implicit none

    type seg_tree
        integer(int64):: n,n2
        integer(int64),pointer:: v(:)
    contains
        procedure:: init => st_init
        procedure:: update => st_update
        procedure:: query => st_query
        procedure:: at => st_at
    end type
contains
    function f(a,b) result(ret)
        integer(int64):: a,b,ret
        ret = min(a,b)
    end function

    subroutine st_init(st, n)
        class(seg_tree):: st
        integer(int64),intent(in):: n
        integer(int64):: x
        x=1
        do while(n > x)
            x = 2*x
        end do
        st%n = x
        st%n2 = 2*x-1
        allocate(st%v(st%n2), source=10_int64**16)
    end subroutine

    subroutine st_update(st, i, x)
        class(seg_tree):: st
        integer(int64), intent(in):: i
        integer(int64):: ind
        integer(int64), intent(in):: x
        
        ind = i + st%n - 1
        st%v(ind) = x
        do while(ind > 1)
            ind = ind/2
            st%v(ind) = f(st%v(2*ind), st%v(2*ind+1))
        end do
    end subroutine

    function st_query(st, a, b) result(ret)
        class(seg_tree):: st
        integer(int64), intent(in):: a,b
        integer(int64):: ret
        ret = st_query_sub(st, a, b, 1_8, 1_8, st%n)
    end function

    function st_at(st, i) result(ret)
        class(seg_tree):: st
        integer(int64),intent(in):: i
        integer(int64):: ret
        ret = st%v(i+st%n-1)
    end function

    recursive function st_query_sub(st, a, b, k, l, r) result(ret)
        type(seg_tree),intent(in):: st
        integer(int64),intent(in):: a,b,k,l,r
        integer(int64):: ret, vl, vr

        if (r < a .or. b < l) then
            ret = 10_int64**16
        else if (a <= l .and. r <= b) then
            ret = st%v(k)
        else
            vl = st_query_sub(st,a,b,k*2, l, (l+r)/2)
            vr = st_query_sub(st,a,b,k*2+1, (l+r)/2+1, r)
            ret = f(vl,vr)
        end if
    end function
end module

program main
    use,intrinsic :: iso_fortran_env
    use segment_tree_mod
    implicit none
    integer(int64):: n,nq
    integer(int64):: i,ans,v
    integer(int64), allocatable:: q(:,:)
    type(seg_tree):: x_st, y_st

    read*, n,nq
    allocate(q(2,nq))
    do i=1,nq
        read*, q(:,i)
    end do

    ans = (n-2)*(n-2)
    call x_st%init(n)
    call y_st%init(n)
    do i=1,n-1
        call x_st%update(i,10_int64**16)
        call y_st%update(i,10_int64**16)
    end do
    call x_st%update(n,n)
    call y_st%update(n,n)

    do i=1,nq
        if (q(1,i) == 1) then
            v = x_st%query(q(2,i),n)
            ! print'("v: ",i0)', v
            ans=ans-(v-2)
            call y_st%update(v,min(y_st%at(v),q(2,i)))
        else
            v = y_st%query(q(2,i),n)
            ! print'("v: ",i0)', v
            ans=ans-(v-2)
            call x_st%update(v,min(x_st%at(v),q(2,i)))
        end if
        ! print'(i0)', ans
    end do
    print'(i0)', ans
end program main