#include "validation.h"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <numeric>
#include <vector>
using namespace std;

constexpr long long MOVES = 200'000;

template <class T>
struct FenwickTree { // Use 0 based indices.
	int n;
	vector<T> tree;
	FenwickTree(int n_) : n(n_ + 1) { tree.assign(n + 1, 0); }
	template <typename F>
	FenwickTree(int n, F f) : n(n) {
		tree.assign(n + 1, 0);
		for(int b = 1; b <= n; b *= 2)
			for(int i = b; i <= n; i += 2 * b) {
				tree[i] += f(i - 1);
				if(i + b <= n) tree[i + b] += tree[i];
			}
	}
	T query(int r) const { // [0, r]
		assert(r + 1 <= n);
		T s = 0;
		for(++r; r > 0; r -= (r & (-r))) s += tree[r];
		return s;
	}
	void update(int i, T v) {
		for(++i; i <= n; i += (i & (-i))) tree[i] += v;
	}
};

using T = int;
T op(T l, T r) {
	return max(l, r);
}
struct SegmentTree {
	int n;
	vector<T> tree;
	T id;
	// Pass the identity here and to initialization using repeated updates.
	SegmentTree(int _n, T _id) : n(_n + 1), tree(2 * n, _id), id(_id) {}
	void update(int i, T val) {
		++i;
		for(tree[i + n] = val, i = (i + n) / 2; i > 0; i /= 2)
			tree[i] = op(tree[2 * i], tree[2 * i + 1]);
	}
	T query(int l, int r) {
		++l, ++r; // [l, r]
		T lhs = T(id), rhs = T(id);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) lhs = op(lhs, tree[l++]);
			if(!(r & 1)) rhs = op(tree[r--], rhs);
		}
		return op(l == r ? op(lhs, tree[l]) : lhs, rhs);
	}
};

long long solve(vector<int>& h, vector<int>& g) {
	auto n = h.size();
	vector<int> ph(n), pg(n);
	iota(begin(ph), end(ph), 0);
	iota(begin(pg), end(pg), 0);

	stable_sort(begin(ph), end(ph), [&](int i, int j) { return h[i] < h[j]; });
	stable_sort(begin(pg), end(pg), [&](int i, int j) { return g[i] < g[j]; });
	// ph[i] and pg[i] now indicate the position of the i'th smallest element in h and g.

	FenwickTree<int> ht(n), gt(n);

	// For each height h that moves from position i to j, compute the number of taller people to
	// the left of it. Add the difference to the answer.
	long long ans = 0;
	for(int k = 0; k < n; ++k) {
		// i moves to position j
		int i = ph[k];
		int j = pg[k];

		ht.update(i, 1);
		gt.update(j, 1);

		ans += abs((i - ht.query(i)) - (j - gt.query(j)));
	}

	return ans;
}

int main(int argc, char** argv) {
	std::ifstream in(argv[1]);
	std::ifstream ans(argv[2]);
	OutputValidator v(argc, argv);

	long long n;
	in >> n;
	long long ans_moves;
	ans >> ans_moves;
	auto answer = v.read_integer("answer", ans_moves, ans_moves);
	v.newline();

	vector<int> h(n), g(n);
	for(auto& x : h) in >> x;
	for(auto& x : g) in >> x;

	SegmentTree st(n, 0);
	for(int i = 0; i < n; ++i) st.update(i, h[i]);

	for(int step = 0; step < std::min(ans_moves, MOVES); ++step) {
		int a = v.read_integer("a", 1, n) - 1;
		v.space();
		int b = v.read_integer("b", 1, n) - 1;
		v.newline();
		v.check(a != b, "Swap must swap different positions.");
		v.check(st.query(min(a, b) + 1, max(a, b) - 1) < min(h[a], h[b]), "Invalid swap of ", h[a],
		        " and ", h[b], " at positions ", a, " and ", b);
		swap(h[a], h[b]);
		st.update(a, h[a]);
		st.update(b, h[b]);
	}

	if(ans_moves <= MOVES) {
		v.check(h == g, "Swaps did not result in the right permutation");
	} else {
		// Compute number of steps remaining.
		v.check(MOVES + solve(h, g) == ans_moves, "Swaps are not optimal");
	}
}