689_D. Friends and Subsequences
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 <image> while !Mike can instantly tell the value of <image>.

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 <image> 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 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence a.

The third line contains n integer numbers b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) — the sequence b.

Output

Print the only integer number — the number of occasions the robot will count, thus for how many pairs <image> 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.
```python
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()    


```