Dragons#11766
In ancient times, when dragons were not legends, to tame a dragon, one had to engage in a mental battle with it! When Chmyyyaks was taming his dragon, he gave it the following task. He solved it very quickly, but can you?
Two arrays of length are given. Let us define a good pair of subsegments of different arrays l_1, r_1 — a subsegment of the first array (denoted as ) and l_2, r_2 — a subsegment of the second array (denoted as ), satisfying the following properties:
|c| = |d| — they have the same length.
\sum_{i = 1}^{|c|} f(c_i - d_i) = 0, where f(x) = \begin{cases} 1, & x > 0 \\ 0, & x = 0 \\ -1, & x < 0 \end{cases}
In short, your task is simple — count the number of good pairs of subsegments.
The first line contains exactly one integer n \ (1 \le n \le 10000) — the length of two arrays.
The second line contains integers a_i \ (0 \le a_i \le 10^9) — the elements of the first array.
The third line contains integers b_i \ (0 \le b_i \le 10^9) — the elements of the second array.
Output only one integer – the answer to the problem.
Example 1
Example 2
In the first sample:
a pair of subsegments [(1,1),(2,2)] is bad, cause f(8-5) = 1 \neq 0;
a pair of subsegments [(1,2),(2,3)] is good, because f(8-5) + f(1-2) = f(3) + f(-1) = 0.
In total there are good pairs of subsegments: \{ [(1,2),(1,2)], [(1,2),(2,3)], [(2,3),(1,2)], [(2,3),(2,3)] \}.
( points): n \le 100;
( points): n \le 500;
( points): n \le 1000,\ a_i \le 100;
( points): n \le 5000;
( points): no additional constraints;