왕

시간 제한2초메모리 제한128 MB

요약

N명의 엘프가 각자 지정된 드워프를 상대로 입장하며, 자리가 차 있으면 시계 방향으로 다음 빈자리를 찾아 앉는다. 입장 순서를 정해 엘프가 이기는 대결 수를 최대로 만들어야 한다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 유니온 파인드, 구현
정답자: 아직 제출이 없습니다

문제

젊은 통치자 미르코가 스스로 난쟁이의 왕이라고 선언했다. 이 소식을 들은 슬라브코는 위협을 느껴 곧바로 자신이 요정의 왕이라고 맞선언했다. 한 땅에 왕이 둘일 수는 없으니, 두 사람은 누가 왕인지를 완전히 끝내기로 했다.

슬라브코는 왕국에서 가장 강한 요정 $N$ 명을 데리고 미르코의 성으로 간다. 요정에게는 $1$ 번부터 $N$ 번까지 번호가 붙어 있다. 성의 홀에는 가장 강한 난쟁이 $N$ 명이 원을 이루어 앉아 있고, 시계 방향으로 $1$ 번부터 $N$ 번까지 번호가 붙어 있다.

미르코는 성에 들어온 요정마다 상대할 난쟁이의 번호 $A_i$ 를 하나씩 정해 주었다. 상대가 겹치지 않도록 신경 쓰지 않았기 때문에 곧 큰 싸움이 벌어졌다.

두 사람은 다음 방식으로 문제를 해결하기로 했다.

슬라브코는 요정을 한 명씩 홀로 들여보낸다. 순서는 슬라브코가 정한다. 앞의 요정이 앉을 자리를 찾은 뒤에야 다음 요정이 들어간다.
$k$ 번 요정은 먼저 $A_k$ 번 난쟁이에게 다가간다. 그 난쟁이 옆에 앉은 요정이 없으면 거기에 앉는다. 이미 다른 요정이 앉아 있으면 시계 방향으로 난쟁이를 한 명씩 지나가며 아직 아무도 앉지 않은 난쟁이를 찾을 때까지 걷는다.

이렇게 짝지어진 $N$ 쌍이 팔씨름으로 겨루고, 힘이 센 쪽이 항상 이긴다.

슬라브코는 모든 참가자의 힘을 미리 조사해 두었다. 요정이 전부 앉았을 때 자기 쪽 승리가 가장 많아지도록 요정을 들여보내는 순서를 정하려고 한다.

요정이 얻을 수 있는 최대 승리 횟수를 구하여라.

입력

첫째 줄에 정수 $N$ 이 주어진다. ( $1 \le N \le 5 \times 10^5$ )

둘째 줄에 미르코가 정한 상대의 번호 $A_1, A_2, \dots, A_N$ 이 주어진다. ( $1 \le A_i \le N$ )

셋째 줄에 난쟁이의 힘 $P_1, P_2, \dots, P_N$ 이 주어진다. ( $1 \le P_i \le 10^9$ )

넷째 줄에 요정의 힘 $V_1, V_2, \dots, V_N$ 이 주어진다. ( $1 \le V_i \le 10^9$ )

입력으로 주어지는 힘 $2N$ 개는 모두 서로 다르다.

출력

요정이 얻을 수 있는 최대 승리 횟수를 첫째 줄에 출력한다.

힌트

첫 번째 예제에서 슬라브코는 요정을 $3, 2, 1$ 순서로 들여보낼 수 있다. 요정 $3$ 은 난쟁이 $3$ 옆에 앉고, 요정 $2$ 는 시계 방향으로 한 자리 옮겨 난쟁이 $1$ 옆에 앉으며, 요정 $1$ 은 난쟁이 $2$ 옆에 앉는다. 요정 $1$ 과 요정 $2$ 가 팔씨름에서 이기고, 요정 $3$ 은 진다.

예제3

예제 1
입력
```
3
2 3 3
4 1 10
2 7 3
```
예상 출력
```
2
```
예제 2
입력
```
4
3 1 3 3
5 8 7 10
4 1 2 6
```
예상 출력
```
1
```
예제 3
입력
```
3
1 2 3
8 4 3
9 2 6
```
예상 출력
```
2
```