A. Hatchet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Frunza verde de mohor,

Te iubesc si te ador,

Ghita C. Topor

— Mihail Sadoveanu, Baltagul

After reading the book "Baltagul" by Mihail Mihai Sadoveanu, Ucselupaert is very angry at "Evaluatorul infoarena" and decided to beat him at Mortal Kombat 11.

You are given two arrays $$$A$$$ and $$$B$$$ both of length $$$N$$$. We call a pair $$$(i,j)$$$ winning if and only if $$$1 \le i \le j \le N$$$ and $$$max(B_{i...j}) \ge max(A_{i...j})$$$ where $$$i...j$$$ denotes the subarray with left and right endpoints $$$(i,j)$$$. Find the number of winning pairs.

Input

The input consists of a number $$$N$$$ representing the number of elements in the array. On the second and third line there will be the values of $$$A$$$ and $$$B$$$ in this order.

Output

Print one integer : the number of winning pairs.

Scoring
  • $$$N \le 10^6$$$ , $$$-10^9 \le A_i , B_i \le 10^9$$$
  • Subtask 1 ( 10 points ) : $$$N \le 10^2$$$
  • Subtask 2 ( 10 points ) : $$$N\le 10^3$$$
  • Subtask 3 ( 50 points ) : $$$N \le 10^5$$$
  • subtask 4 ( 30 ponts ) : no further constrains
Example
Input
5
3 1 4 2 2
5 2 1 3 2
Output
9