사랑은 전쟁

우정이와 아름이는 열렬히 사랑하고 있다. 두 사람의 사랑을 증명하기 위해 당신은 궁합 테스트를 만들었다. 두 사람은 각각 길이가 $N$이고 각 원소가 $1$ 이상 $N$ 이하인 수열을 생각한다. 궁합 테스트는 우정이의 수열 $A$와 아름이의 수열 $B$로 LOVE 점수를 계산하며, 방법은 다음과 같다.

$f(l \ldots r)$ = ($A_i=B_j=x$ 인 $l\leq i,j\leq r$이 존재하는 $x$의 최댓값, 그런 $x$가 없으면 $0$)이다. 즉, $f(l \ldots r)$은 $A[l \ldots r]$과 $B[l \ldots r]$에 모두 나타나는 수 중 가장 큰 값이다. 두 구간에 공통으로 나타나는 수가 없으면 0이다.

LOVE 점수 = $\sum_{1\leq l\leq r\leq N}f(l \ldots r)$이다. 가능한 모든 $\binom{N+1}{2}$개의 구간에 대한 $f$ 값의 합이다.

첫 번째 줄에 수열의 길이 $N$이 주어진다.

두 번째 줄에 우정이의 수열 $A_i$ ($1 \leq i \leq N$)가 공백으로 구분되어 주어진다.

세 번째 줄에 아름이의 수열 $B_i$ ($1 \leq i \leq N$)가 공백으로 구분되어 주어진다.

우정이와 아름이의 LOVE 점수를 출력한다.

• $N \leq 500,000$
• $1 \leq A_i,B_i \leq N$ ($1 \leq i \leq N$)
• 입력으로 주어지는 모든 수는 정수이다.

일부 테스트 케이스는 답이 $2^{31}$을 넘을 수 있으므로 long long 자료형을 사용한다.