Драконы

В древние времена, когда драконы еще не были легендами, чтобы приручить дракона, нужно было вступить с ним в умственное сражение! Когда Чмыяк приручал своего дракона, он дал ему следующую задачу. Он решил ее очень быстро, но сможете ли вы?

Даны два массива длины $n$. Определим хорошую пару подотрезков разных массивов $l_1,r_1$ — подотрезок первого массива (обозначим его как $c$) и $l_2,r_2$ — подотрезок второго массива (обозначим его как $d$), удовлетворяющие следующим свойствам:

1. $|c|=|d|$ — они имеют одинаковую длину.

2. ${\sum }_{i=1}^{|c|}f(c_i-d_i)=0$, где $f(x)=\{\begin{array}{ll}1,& x>0\\ 0,& x=0\\ -1,& x<0\end{array}$

Ваша задача проста — посчитать количество хороших пар подотрезков.

Входные данные

Первая строка содержит ровно одно целое число $n(1\le n\le 10000)$ — длину двух массивов.

Вторая строка содержит $n$ целых чисел $a_i(0\le a_i\le 10^9)$ — элементы первого массива.

Третья строка содержит $n$ целых чисел $b_i(0\le b_i\le 10^9)$ — элементы второго массива.

Выходные данные

Выведите только одно целое число – ответ на задачу.

Примеры

Примечание

В первом примере

1. пара подотрезков $[(1,1),(2,2)]$ плохая, потому что $f(8-5)=1\ne 0$;

2. пара подотрезков $[(1,2),(2,3)]$ хорошая, потому что $f(8-5)+f(1-2)=f(3)+f(-1)=0$.

Всего есть 4 хорошие пары подотрезков: $\{[(1,2),(1,2)],[(1,2),(2,3)],[(2,3),(1,2)],[(2,3),(2,3)]\}$.

Оценивание

1. ($7$ баллов): $n\le 100$;

2. ($14$ баллов): $n\le 500$;

3. ($22$ баллов): $n\le 1000,a_i\le 100$;

4. ($31$ баллов): $n\le 5000$;

5. ($26$ баллов): без дополнительных ограничений;