31745번 - Love is War 서브태스크

문제

우정이와 아름이는 열렬한 사랑을 하고 있다. 우정이와 아름이의 사랑을 증명하기 위해 당신은 궁합 테스트를 만들었다. 우정이와 아름이는 각각 길이가 $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$값의 합이다.

사랑은 전쟁이다. 우정이와 아름이는 누가 더 서로를 사랑하는지 대결하려고 LOVE 점수를 최대한 빨리 구하려고 했다. 하지만 $N$은 우정이와 아름이의 사랑보다 큰 것 같다. 대신 당신이 두 수열 $A,B$가 주어졌을 때 LOVE 점수를 직접 구해보자.

입력

첫 번째 줄에 우정이와 아름이의 수열의 길이 $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 자료형을 쓰도록 하자.