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
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)

struct Tree {
	int a[500000];
	int l[500000];
	int r[500000];
	int h;
};

const int mod = 1000000007;
int n;
Tree t1, t2;

void prep(Tree& t) {
	REP(i,n)
		if (t.a[i] > 0) --t.a[i];
		else t.h = i;
	REP(i,n) t.l[i] = t.r[i] = -1;
	REP(i,n)
		if (t.a[i] > i) t.l[t.a[i]] = i;
		else if (t.a[i] >= 0) t.r[t.a[i]] = i;
}

int fix(Tree* t, int h) {
	if (h < 0) return 0;
	int res = (fix(t, t->l[h]) + fix(t, t->r[h])) % mod;
	res = (res + abs(h - t->a[h]) - 1) % mod;
	return res;
}

int rots(Tree* t1, int h1, Tree* t2, int h2) {
	if (h1 < 0 || h2 < 0) return 0;
	if (h1 > h2) {
		swap(t1, t2);
		swap(h1, h2);
	}
	int x1 = h1, y1 = h1, x2 = h2, y2 = h2;
	while (y1 < h2) y1 = t1->r[y1];
	while (x2 > h1) x2 = t2->l[x2];
	while (x1 != x2)
		if (x1 < x2) x2 = t2->l[x2];
		else x1 = t1->l[x1];
	while (y1 != y2)
		if (y1 < y2) y1 = t1->r[y1];
		else y2 = t2->r[y2];
	int res = h2 - h1;
	for (int i = t1->l[h1]; i >= 0 && i >= x1; i = t1->l[i])
		res = ((res + fix(t1, t1->r[i])) % mod + t1->a[i] - i - 1) % mod;
	for (int i = t2->l[h2]; i >= 0 && i >= x2; i = t2->l[i])
		res = ((res + fix(t2, t2->r[i])) % mod + t2->a[i] - i - 1) % mod;
	for (int i = t1->r[h1]; i >= 0 && i <= y1; i = t1->r[i])
		res = ((res + fix(t1, t1->l[i])) % mod + i - t1->a[i] - 1) % mod;
	for (int i = t2->r[h2]; i >= 0 && i <= y2; i = t2->r[i])
		res = ((res + fix(t2, t2->l[i])) % mod + i - t2->a[i] - 1) % mod;
	res = (res + rots(t1, t1->l[x1], t2, t2->l[x2])) % mod;
	res = (res + rots(t1, t1->r[y1], t2, t2->r[y2])) % mod;
	return res;
}

int main() {
	INT(n1);
	n = n1;
	REP(i,n) scanf("%d", &t1.a[i]);
	REP(i,n) scanf("%d", &t2.a[i]);
	prep(t1);
	prep(t2);
	printf("%d\n", rots(&t1, t1.h, &t2, t2.h));
}