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.
#include <bits/stdc++.h>
using namespace std;
struct Segment_Tree {
  int mx[200003 << 2], mn[200003 << 2], a[200003];
  int qmax(int nl, int nr, int l, int r, int u) {
    if (nl <= l && r <= nr) return mx[u];
    int res = -0x3f3f3f3f, mid = (l + r) >> 1;
    if (nl <= mid) res = max(res, qmax(nl, nr, l, mid, (u << 1)));
    if (nr > mid) res = max(res, qmax(nl, nr, mid + 1, r, (u << 1 | 1)));
    return res;
  }
  int qmin(int nl, int nr, int l, int r, int u) {
    if (nl <= l && r <= nr) return mn[u];
    int res = 0x3f3f3f3f, mid = (l + r) >> 1;
    if (nl <= mid) res = min(res, qmin(nl, nr, l, mid, (u << 1)));
    if (nr > mid) res = min(res, qmin(nl, nr, mid + 1, r, (u << 1 | 1)));
    return res;
  }
  void build(int l, int r, int u) {
    if (l == r) {
      mx[u] = mn[u] = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (u << 1)), build(mid + 1, r, (u << 1 | 1));
    mx[u] = max(mx[(u << 1)], mx[(u << 1 | 1)]);
    mn[u] = min(mn[(u << 1)], mn[(u << 1 | 1)]);
  }
};
Segment_Tree A, B;
int n;
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i) scanf("%d", &A.a[i]);
  for (register int i = 1; i <= n; ++i) scanf("%d", &B.a[i]);
  A.build(1, n, 1), B.build(1, n, 1);
  long long x0, x1, ans = 0;
  for (register int i = 1; i <= n; ++i) {
    long long l = i, r = n, mid;
    while (l < r) {
      mid = (l + r) >> 1;
      if (A.qmax(i, mid, 1, n, 1) >= B.qmin(i, mid, 1, n, 1))
        r = mid;
      else
        l = mid + 1;
    }
    if (A.qmax(i, r, 1, n, 1) != B.qmin(i, r, 1, n, 1)) continue;
    x0 = r;
    r = n, l = x0;
    while (l < r) {
      mid = (l + r) >> 1;
      if (A.qmax(i, mid, 1, n, 1) > B.qmin(i, mid, 1, n, 1))
        r = mid;
      else
        l = mid + 1;
    }
    if (A.qmax(i, r, 1, n, 1) == B.qmin(i, r, 1, n, 1))
      x1 = r;
    else
      x1 = r - 1;
    ans += x1 - x0 + 1;
  }
  printf("%lld\n", ans);
}
