409567: GYM103633 A Hatchet

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.

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.

Print one integer : the number of winning pairs.

• $$$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

5
3 1 4 2 2
5 2 1 3 2

9