31028번 - 순열의 개수

문제

동현이와 정후는 밤하늘을 보고 있다.

• 동현: 정후야, 저 밤하늘을 봐. 오리온자리야! 마치 길이가 $N$인 두 순열이 교차하는 것 같지 않니?
• 정후: 뭐라고?
• 동현: 길이가 $N$인 두 순열 $A_1, A_2, \cdots, A_N$와 $B_1, B_2, \cdots, B_N$을 생각해 보자. 수열 $A$에서 제일 앞 $i$개의 수를 고르고, $B$에서 제일 앞 $j$개의 수를 골라 일렬로 나열했을 때 길이 $i+j$의 순열이 되는 경우는 몇 가지일까? $i, j$의 범위는 0ドル$ 이상 $N$ 이하야.
• 정후: 간단하지! 그건...

...이라고 대답해 버렸다. 정후를 도와 동현이의 퀴즈를 풀어 주자. 단, 길이 $M$의 순열이란 0ドル$ 이상 $M$ 미만의 수가 정확히 한 번씩 등장하는 수열이다. 길이 0ドル$의 수열도 순열이다.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다. 두 번째 줄에 수열 $A,ドル 세 번째 줄에 수열 $B$가 주어진다. 0ドル\leq A_i, B_i < N$ 이며, $i\neq j$일 때, $A_i\neq A_j, B_i\neq B_j$ 이다.

출력

동현이의 퀴즈에 대한 답을 출력한다.

제한

• 1ドル\leq N\leq 5\times10^5$
• 주어지는 모든 수는 정수이다.

힌트