Дракони

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

Дані два масиви довжини $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$ балів): без додаткових обмежень;