1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define cat(x) cerr << #x << " = " << x << endl
#define IOS cin.tie(0); ios_base::sync_with_stdio(0)
 
using ll = long long;
using namespace std;

const int N = 1 << 19;

int n, ans;
int p[N], l[N], r[N], a[N], b[N];

void leftrotation(int v, int u) {
	ans++;
	if (p[v] != -1) {
		if (r[p[v]] == v)
			r[p[v]] = u;
		else
			l[p[v]] = u;
	}
	p[u] = p[v];
	p[v] = u;
	l[u] = v;
	r[v] = 0;
}

void rightrotation(int v, int u) {
	ans++;
	if (p[v] != -1) {
		if (r[p[v]] == v)
			r[p[v]] = u;
		else
			l[p[v]] = u;
	}
	p[u] = p[v];
	p[v] = u;
	r[u] = v;
	l[v] = 0;
}

void rec(int v, int u) {
	while (v != u) {
		if (v < u) {
			rec(r[v], v + 1);
			leftrotation(v, r[v]);
			v++;
		}	
		else {
			rec(l[v], v - 1);
			rightrotation(v, l[v]);
			v--;
		}	
	}
}

void fix(int v, int u) {
	if (!v) return;
	rec(v, u);
	fix(l[u], a[u]);
	fix(r[u], b[u]);
}

int main() {
	scanf("%d", &n);
	int r0, r1;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", p + i);
		if (p[i] == -1)
			r0 = i;
		else if (i < p[i])
			l[p[i]] = i;
		else
			r[p[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		int w;
		scanf("%d", &w);
		if (w == -1) 
			r1 = i;
		else if (i < w)
			a[w] = i;
		else
			b[w] = i;
	}
	fix(r0, r1);
	printf("%d\n", ans);
	return 0;
}