mixperm

Se consideră două șiruri de numere naturale, ambele de lungime $n$, $a$ = ($a_1$, $a_2$, $\dots$, $a_n$ și $b$ = ($b_1$, $b_2$, $\dots$, $b_n$). Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea {$1$, $2$, $\dots$, $n$}. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici $i$ și $j$, cu $1 \leq i \leq j \leq n$ , apoi prin interschimbarea secvențelor $a_i$, $a_{i+1}$, $\dots$, $a_j$ cu $b_i$, $b_{i+1}$, $\dots$, $b_j$ se obțin șirurile: $a_1$, $a_2$, $\dots$, $a_{i-1}$, $b_i$ ,$b_{i+1}$, $\dots$, $b_j$, $a_{j+1}$, $a_{j+2}$, $\dots$, $a_n$ și $b_1$, $b_2$, $\dots$, $b_{i-1}$, $a_i$ ,$a_{i+1}$, $\dots$, $a_j$, $b_{j+1}$, $b_{j+2}$, $\dots$, $b_n$

Dacă măcar unul din șirurile obținute este permutare a mulțimii {$1$, $2$, $\dots$, $n$}, atunci spunem că s-a obținut un mixperm.

Cerinţa

Să se determine în câte moduri se poate obține un mixperm.

Date de intrare

Fişierul mixperm.in conţine pe prima linie numărul natural $n$, pe linia a doua, separate prin câte un spațiu, numerele $a_1$, $a_2$, $\dots$, $a_n$, iar pe linia a treia, separate prin câte un spațiu, numerele $b_1$, $b_2$, $\dots$, $b_n$.

Date de ieșire

Fişierul mixperm.out conţine un singur număr natural reprezentând numărul de posibilități de a se obține un mixperm.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$;

Exemplul 1

mixperm.in

6
3 2 1 4 4 5
2 3 3 4 6 5

mixperm.out

8

Explicație

Se pot interschimba secvențele care au ca poziții de început și sfârșit $(1, 3)$, $(1, 4)$, $(3, 3)$, $(3, 4)$, $(4, 6)$, $(5, 6)$, $(4, 5)$, $(5, 5)$.

Exemplul 2

mixperm.in

2
1 2
1 2

mixperm.out

3

Explicație

Se pot interschimba secvențele care au ca poziții de început și sfârșit $(1, 1)$, $(2, 2)$ și $(1, 2)$.