물정수열 2

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

요약

각 시험에서 세 과목 점수 중 하나만 바꿔 중앙값 수열이 엄격히 증가하는 부분수열의 최대 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색
정답자: 아직 제출이 없습니다

문제

경기북과학고등학교에서는 물리, 정보, 수학 세 과목에 대해서만 시험을 본다. 이제 곧 학교를 졸업하는 래오는 학교생활 동안 치른 $N$ 번의 시험을 바탕으로 포트폴리오를 작성하려 한다. 래오는 자신의 성적이 너무 낮아 보이는 것도, 높아 보이는 것도 원하지 않기 때문에 세 과목의 성적 중 중앙값을 순서대로 포트폴리오에 적을 것이다.

또한 래오는 포트폴리오에 적힌 성적이 점점 증가하기를 원한다. 성적이 같은 경우는 허용되지 않으며, 반드시 증가해야 한다. 아쉽게도 래오의 현재 성적표로는 이를 만족하지 못할 수 있기 때문에, 래오는 친구 지훈이의 힘을 빌려 목표를 이루려 한다. 지훈이는 각 시험당 최대 한 과목의 점수를 원하는 점수로 바꿔 줄 수 있다. 경기북과학고등학교의 시험 점수는 항상 음이 아닌 정수이기 때문에, 바뀐 점수 역시 음이 아닌 정수여야 한다.

하지만 이조차 항상 가능하지는 않다는 것을 알게 되었다. 대신 래오는 포트폴리오의 최장 증가 부분 수열(LIS) 길이를 최대화하려 한다. 지훈이의 도움을 적절히 받아 만들 수 있는 포트폴리오의 LIS 길이의 최댓값을 구하여라.

입력

첫 번째 줄에 시험의 개수 $N$ 이 주어진다. $(1 \leq N \leq 200\,000)$

두 번째 줄에 각 시험에서의 물리 점수 $A_1, A_2, \cdots, A_N$ 이 순서대로 공백으로 구분되어 주어진다. $(0 \leq A_i \leq 2 \times 10^9)$

세 번째 줄에 각 시험에서의 정보 점수 $B_1, B_2, \cdots, B_N$ 이 순서대로 공백으로 구분되어 주어진다. $(0 \leq B_i \leq 2 \times 10^9)$

네 번째 줄에 각 시험에서의 수학 점수 $C_1, C_2, \cdots, C_N$ 이 순서대로 공백으로 구분되어 주어진다. $(0 \leq C_i \leq 2 \times 10^9)$

시험 점수는 모두 정수이다.

출력

포트폴리오에서 만들 수 있는 최장 증가 부분 수열 길이의 최댓값을 출력한다.

예제3

예제 1
입력
```
3
1 2 3
0 4 3
5 3 3
```
예상 출력
```
3
```
예제 2
입력
```
4
1 2 3 2
0 3 3 2
4 3 5 3
```
예상 출력
```
3
```
예제 3
입력
```
2
1 0
0 0
1 0
```
예상 출력
```
1
```