409567: GYM103633 A Hatchet

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Hatchettime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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
ExampleInput
5
3 1 4 2 2
5 2 1 3 2
Output
9

加入题单

上一题 下一题 算法标签: