#include <stdio.h>
#include <vector>
#include <assert.h>
using namespace std;
#define MAXHW 1000000

#define PM_(b) (b?+1:-1)
int H,W;

//subtask 5, H=1

int NUM[MAXHW];
char D[MAXHW];

struct Node {
public:
    int lowest=-1;
    int lowest_count=-1;
    int total_effect=0;
    Node* left;
    Node* right;
    Node* L() {return left?left:left=new Node();}
    Node* R() {return right?right:right=new Node();}

    int count_zeroes() {
        return lowest?0:lowest_count;
    }

    void build(int l, int r) {
        if(l==r) {
            lowest = total_effect = D[l];
            lowest_count = 1;
            return;
        }
        int m = (l+r)>>1;
        L()->build(l,m);
        R()->build(m+1,r);
        int ll=left->lowest, lr=right->lowest;
        if(ll<lr)
            lowest = ll, lowest_count = left->lowest_count;
        else if(ll>lr)
            lowest = lr, lowest_count = right->lowest_count;
        else
            lowest = ll, lowest_count = left->lowest_count + right->lowest_count;
        total_effect = left->total_effect+right->total_effect;
    }

    void update_self() {
        int ll=left->lowest, lr=right->lowest;
        if(ll<lr)
            lowest = ll, lowest_count = left->lowest_count;
        else if(ll>lr)
            lowest = lr, lowest_count = right->lowest_count;
        else
            lowest = ll, lowest_count = left->lowest_count + right->lowest_count;
        total_effect = left->total_effect+right->total_effect;
    }

    void update(int l, int r, int t, int nv) {
        if(l==r) {
            assert(l==t);
            lowest = nv;
            total_effect = nv;
            return;
        }
        int m = (l+r)>>1;
        if(t>m) {
            right->update(m+1,r,t,nv);
        }
        else {
            int oldval = left->total_effect;
            left->update(l,m,t,nv);
            right->lowest += left->total_effect-old_val;
        }
        update_self();
    }

    static Node* make_tree(int l, int r) {
        Node* n = new Node();
        n->build(l,r);
        return n;
    }
};

Node* root = nullptr;

vector<int> R;
vector<int> C;

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) { //R,C is the row and col of seat #i
    assert(h==1); //R[i]==1,foreach i
    R=r;
    C=c;
    H=h,W=w;
    for(int i=0;i<w;i++)
        NUM[C[i]] = i;
    if(w==1) {
        D[0]=0; return;
    }
    D[0] = NUM[1]>NUM[0]?1:0;
    for(int i=1;i<w-1;i++)
        D[i] = PM_(NUM[i-1]>NUM[i])+PM_(NUM[i+1]>NUM[i]);
    D[w-1]=NUM[w-2]>NUM[w-1]?1:0;
    root = Node::make_tree(0,w-1);
}

void swap_seats(int a, int b) {
    int x=C[a],y=C[b];
    std::swap(NUM[x],NUM[y]);
    vector<pair<int,int>> u; //{nv, pos}

}