순열의 개수

시간 제한1초메모리 제한1024 MB

요약

0 이상 N 이하인 i, j에 대해 순열 A의 앞 i개와 순열 B의 앞 j개를 이어 붙인 수열이 길이 i+j인 순열이 되는 쌍의 개수를 구한다.

문제

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

동현: 정후야, 저 밤하늘을 봐. 오리온자리야! 마치 길이가 $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$ 이다.

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