In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $p$ of length $n$ to the zoo.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ occurs twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ is present in the array).

The gorillas had their own permutation $q$ of length $n$. They suggested that you count the number of pairs of integers $l, r$ ($1 \le l \le r \le n$) such that $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$.

The $\operatorname{MEX}$ of the sequence is the minimum integer positive number missing from this sequence. For example, $\operatorname{MEX}([1, 3]) = 2$, $\operatorname{MEX}([5]) = 1$, $\operatorname{MEX}([3, 1, 2, 6]) = 4$.

You do not want to risk your health, so you will not dare to refuse the gorillas.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the permutations length.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the elements of the permutation $p$.

The third line contains $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le n$) — the elements of the permutation $q$.


-----Output-----

Print a single integer — the number of suitable pairs $l$ and $r$.


-----Examples-----

Input
3
1 3 2
2 1 3
Output
2
Input
7
7 3 6 2 1 5 4
6 7 2 5 3 1 4
Output
16
Input
6
1 2 3 4 5 6
6 5 4 3 2 1
Output
11


-----Note-----

In the first example, two segments are correct – $[1, 3]$ with $\operatorname{MEX}$ equal to $4$ in both arrays and $[3, 3]$ with $\operatorname{MEX}$ equal to $1$ in both of arrays.

In the second example, for example, the segment $[1, 4]$ is correct, and the segment $[6, 7]$ isn't correct, because $\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Dynamic programming

Mathematics
Skill types: Dynamic programming

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	p = list(map(int, inp().split()))
	q = list(map(int, inp().split()))
	pi = [None] * (n + 1)
	qi = [None] * (n + 1)
	for i in range(n):
		pi[p[i]] = i
		qi[q[i]] = i
	x = pi[1]
	y = qi[1]
	if x > y:
		(x, y) = (y, x)
	res = 0
	if x >= 1:
		res += x * (x + 1) // 2
	if n - 1 - y >= 1:
		res += (n - y - 1) * (n - y) // 2
	if y - x - 1 >= 1:
		res += (y - x - 1) * (y - x) // 2
	l = x
	r = y
	for i in range(2, n):
		x = pi[i]
		y = qi[i]
		if x > y:
			(x, y) = (y, x)
		if not (x >= l and x <= r or (y >= l and y <= r)):
			if y < l:
				u = l - y
			elif x < l:
				u = l - x
			else:
				u = l + 1
			if x > r:
				v = x - r
			elif y > r:
				v = y - r
			else:
				v = n - r
			res += u * v
		l = min(l, x)
		r = max(r, y)
	print(res + 1)

def main():
	solve()
main()


from collections import deque

def getint():
	return int(input())

def getfloat():
	return float(input())

def getints():
	return list(map(int, input().split()))

def getfloats():
	return list(map(float, input().split()))

def getcomb(i):
	return i * (i + 1) // 2

def answer():
	n = getint()
	p = getints()
	q = getints()
	pp = [0] * (n + 1)
	qq = [0] * (n + 1)
	for (i, _p) in enumerate(p):
		pp[_p] = i
	for (i, _q) in enumerate(q):
		qq[_q] = i
	left = min(pp[1], qq[1])
	right = max(pp[1], qq[1])
	ans = getcomb(left) + getcomb(right - left - 1) + getcomb(n - 1 - right)
	for i in range(2, n):
		if left <= pp[i] <= right or left <= qq[i] <= right:
			left = min(pp[i], left, qq[i])
			right = max(pp[i], right, qq[i])
			continue
		leftbound = -1
		rightbound = n
		if pp[i] < left:
			leftbound = max(leftbound, pp[i])
		if pp[i] > right:
			rightbound = min(rightbound, pp[i])
		if qq[i] < left:
			leftbound = max(leftbound, qq[i])
		if qq[i] > right:
			rightbound = min(rightbound, qq[i])
		ans += (left - leftbound) * (rightbound - right)
		left = min(pp[i], left, qq[i])
		right = max(pp[i], right, qq[i])
	print(ans + 1)
T = 1
for i in range(T):
	answer()


def f(l, r, x1, x2, n):
	if x2 < l:
		return (l - x2) * (n - r)
	elif x1 > r:
		return (l + 1) * (x1 - r)
	elif x1 < l and x2 > r:
		return (l - x1) * (x2 - r)
	return 0

def f1(l):
	res = l * (l + 1) // 2
	return res

def solve(p, q):
	n = len(p)
	p_pos = [0] * n
	q_pos = [0] * n
	for ni in range(n):
		p_pos[p[ni] - 1] = ni
		q_pos[q[ni] - 1] = ni
	(x1, x2) = sorted([p_pos[0], q_pos[0]])
	res = 0
	if x1 > 0:
		res += f1(x1)
	if x2 > x1 + 1:
		res += f1(x2 - x1 - 1)
	if x2 < n - 1:
		res += f1(n - 1 - x2)
	l = x1
	r = x2
	for v in range(2, n - 1):
		(x1, x2) = sorted([p_pos[v - 1], q_pos[v - 1]])
		res += f(l, r, x1, x2, n)
		l = min(x1, x2, l)
		r = max(x1, x2, r)
	res += 1
	return res
n = int(input())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
print(solve(p, q))


from sys import stderr

def main(p, q) -> int:
	result = 1
	n = len(p)
	p_inds = {v: i for (i, v) in enumerate(p)}
	q_inds = {v: i for (i, v) in enumerate(q)}
	(one1, one2) = sorted((p_inds[1], q_inds[1]))
	a = one1
	b = one2 - one1 - 1
	c = n - one2 - 1
	result += a * (a + 1) // 2 + b * (b + 1) // 2 + c * (c + 1) // 2
	(left, right) = (one1, one2)
	for mex in range(2, n):
		(mex1, mex2) = sorted((p_inds[mex], q_inds[mex]))
		if mex2 < left:
			result += (left - mex2) * (n - right)
		elif mex1 > right:
			result += (mex1 - right) * (left + 1)
		elif mex1 < left and mex2 > right:
			result += (left - mex1) * (mex2 - right)
		(left, right) = (min(mex1, mex2, left), max(mex1, mex2, right))
	return result
(_, p, q) = (list(map(int, input().split())) for _ in range(3))
assert len(p) == len(q) and set(p) == set(q)
lrs = main(p, q)
print(lrs)


n = int(input())
p = [int(x) for x in input().split(' ')]
q = [int(x) for x in input().split(' ')]
dicp = {}
dicq = {}
for i in range(n):
	dicp[p[i]] = i
	dicq[q[i]] = i
ans = 0
for i in range(1, n + 1):
	if i == 1:
		left = min(dicp[i], dicq[i])
		right = max(dicp[i], dicq[i])
		ans += left * (left - 1) // 2 + left
		ans += (n - 1 - right) * (n - 2 - right) // 2 + (n - 1 - right)
		if left != right:
			ans += (right - 1 - left) * (right - 2 - left) // 2 + (right - 1 - left)
	else:
		l = min(dicp[i], dicq[i])
		r = max(dicp[i], dicq[i])
		if l == r:
			if 0 <= left and right <= l - 1:
				ans += (left + 1) * (l - right)
			if r + 1 <= left and right <= n - 1:
				ans += (left - r) * (n - right)
		else:
			if 0 <= left and right <= l - 1:
				ans += (left + 1) * (l - right)
			if r + 1 <= left and right <= n - 1:
				ans += (left - r) * (n - right)
			if l + 1 <= left and right <= r - 1:
				ans += (left - l) * (r - right)
		left = min(l, left)
		right = max(r, right)
print(ans + 1)


n = int(input())
xs = [int(a) - 1 for a in input().split()]
ys = [int(a) - 1 for a in input().split()]

def invert(xs):
	ret = [0] * len(xs)
	for (i, x) in enumerate(xs):
		ret[x] = i
	return ret
xs = invert(xs)
ys = invert(ys)
intervals = [(min(x, y), max(x, y)) for (x, y) in zip(xs, ys)]
(i, j) = intervals[0]

def c2(x):
	return x * (x - 1) // 2
res = c2(i + 1) + c2(n - j) + c2(abs(xs[0] - ys[0]))

def overlap(r1, r2):
	if r1 > r2:
		(r1, r2) = (r2, r1)
	(a, b) = r1
	(c, d) = r2
	return c <= b
cur = intervals[0]
for i in range(1, n):
	(a, b) = cur
	(c, d) = intervals[i]
	if not overlap(cur, intervals[i]):
		if cur < intervals[i]:
			res += (a + 1) * (c - b)
		else:
			res += (n - b) * (a - d)
	elif c < a and b < d:
		res += (a - c) * (d - b)
	cur = (min(a, c), max(b, d))
res += 1
print(res)


n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
(first, last) = ([n - 1] * (n + 1), [0] * (n + 1))
for (j, v) in enumerate(a):
	first[v] = min(first[v], j)
	last[v] = max(last[v], j)
for (j, v) in enumerate(b):
	first[v] = min(first[v], j)
	last[v] = max(last[v], j)
firstp = first[:]
lastp = last[:]
for j in range(1, n + 1):
	firstp[j] = min(firstp[j - 1], first[j])
	lastp[j] = max(lastp[j - 1], last[j])
counts = [0] * (n + 1)
counts[0] = (first[1] + 1) * first[1] // 2 + (n - last[1] - 1) * (n - last[1]) // 2 + (last[1] - first[1]) * (last[1] - first[1] - 1) // 2
for j in range(n, 1, -1):
	if last[j] < firstp[j - 1]:
		a = firstp[j - 1] - last[j]
		b = n - lastp[j - 1]
	elif first[j] < firstp[j - 1] and last[j] > lastp[j - 1]:
		a = firstp[j - 1] - first[j]
		b = last[j] - lastp[j - 1]
	elif first[j] > lastp[j - 1]:
		a = firstp[j - 1] + 1
		b = first[j] - lastp[j - 1]
	else:
		continue
	counts[j] = a * b
print(sum(counts) + 1)


import sys
import math
input = lambda : sys.stdin.readline().rstrip()
(res, n) = (1, int(input()))
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
(P, Q) = (sorted(((p, i) for (i, p) in enumerate(P))), sorted(((p, i) for (i, p) in enumerate(Q))))
req = [n, -1]
(pi, qi) = (P[0][1], Q[0][1])
(minI, maxI) = (min(pi, qi), max(pi, qi))
res += math.comb(minI + 1, 2)
res += math.comb(maxI - minI, 2)
res += math.comb(n - maxI, 2)
for j in range(1, n):
	req[0] = min(req[0], minI)
	req[1] = max(req[1], maxI)
	(pi, qi) = (P[j][1], Q[j][1])
	(minI, maxI) = (min(pi, qi), max(pi, qi))
	if minI > req[1]:
		res += (1 + req[0]) * (minI - req[1])
	elif maxI < req[0]:
		res += (n - req[1]) * (req[0] - maxI)
	elif minI < req[0] and maxI > req[1]:
		res += (req[0] - minI) * (maxI - req[1])
print(res)