Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows? 

Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l, r), Mike can instantly tell the value of $\operatorname{max}_{i = l}^{r} a_{i}$ while !Mike can instantly tell the value of $\operatorname{min}_{i = l} b_{i}$.

Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l, r) (1 ≤ l ≤ r ≤ n) (so he will make exactly n(n + 1) / 2 queries) and counts how many times their answers coincide, thus for how many pairs $\operatorname{max}_{i = l}^{r} a_{i} = \operatorname{min}_{i = l} b_{i}$ is satisfied.

How many occasions will the robot count?


-----Input-----

The first line contains only integer n (1 ≤ n ≤ 200 000).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the sequence a.

The third line contains n integer numbers b_1, b_2, ..., b_{n} ( - 10^9 ≤ b_{i} ≤ 10^9) — the sequence b.


-----Output-----

Print the only integer number — the number of occasions the robot will count, thus for how many pairs $\operatorname{max}_{i = l}^{r} a_{i} = \operatorname{min}_{i = l} b_{i}$ is satisfied.


-----Examples-----
Input
6
1 2 3 2 1 4
6 7 1 2 3 2

Output
2

Input
3
3 3 3
1 1 1

Output
0



-----Note-----

The occasions in the first sample case are:

1.l = 4,r = 4 since max{2} = min{2}.

2.l = 4,r = 5 since max{2, 1} = min{2, 3}.

There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Data structures


Solutions:
from bisect import bisect
HISENTINEL = 10 ** 9 + 1
LOSENTINEL = -HISENTINEL

def main():
	length = int(input())
	a = [int(fld) for fld in input().strip().split()]
	b = [int(fld) for fld in input().strip().split()]
	print(countmaxminsubseq(a, b))

def countmaxminsubseq(a, b):
	(leq, lgt) = getleftbounds(a, b, 0)
	(req, rgt) = getleftbounds(reversed(a), reversed(b), 1)
	req = reverseindex(req)
	rgt = reverseindex(rgt)
	count = 0
	for (i, (leq1, lgt1, req1, rgt1)) in enumerate(zip(leq, lgt, req, rgt)):
		count += (leq1 - lgt1) * (rgt1 - i) + (i - leq1) * (rgt1 - req1)
	return count

def getleftbounds(a, b, bias):
	astack = [(HISENTINEL, -1)]
	bstack = [(LOSENTINEL, -1)]
	(leqarr, lgtarr) = ([], [])
	for (i, (aelt, belt)) in enumerate(zip(a, b)):
		while astack[-1][0] < aelt + bias:
			astack.pop()
		lgt = astack[-1][1]
		while bstack[-1][0] > belt:
			bstack.pop()
		if belt < aelt:
			leq = lgt = i
		elif belt == aelt:
			leq = i
			istack = bisect(bstack, (aelt, -2)) - 1
			lgt = max(lgt, bstack[istack][1])
		else:
			istack = bisect(bstack, (aelt, i)) - 1
			(val, pos) = bstack[istack]
			if val < aelt:
				lgt = leq = max(lgt, pos)
			else:
				leq = pos
				istack = bisect(bstack, (aelt, -2)) - 1
				(val, pos) = bstack[istack]
				lgt = max(lgt, pos)
				leq = max(leq, lgt)
		leqarr.append(leq)
		lgtarr.append(lgt)
		astack.append((aelt, i))
		bstack.append((belt, i))
	return (leqarr, lgtarr)

def reverseindex(rind):
	pivot = len(rind) - 1
	return [pivot - i for i in reversed(rind)]
main()