Everything Is A Nail

면접 대비

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

요약

세 종류의 도구가 필요한 작업 열이 주어질 때, 도구를 최대 두 번 버리며 완료할 수 있는 작업 수의 최댓값을 구한다.

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

문제

As an employee of the Iffy Colossal Pinnacle Construction (ICPC) company building a very tall skyscraper, you have a number of tasks to complete high above the ground in a specific order. You can always choose to skip a task, but you fear that doing so too many times might cause some catastrophic failure of the building. You cannot revisit or complete a task once it has been skipped.

Each task is a nail, a screw, or a bolt. You have three tools: a hammer (works on nails), a screwdriver (works on screws), and a wrench (works on bolts). When you start a new task you can choose to switch your tool out by dropping it (hopefully no one was below you at the time), but when you do so you permanently lose the dropped tool.

Given the list of tasks in the order they should be completed, determine the maximum number of tasks that can be completed. You may choose to use any tool as the initial tool.

입력

The first line of input contains an integer $n$ ( $1 \leq n \leq 3 \times 10^5$ ), which is the number of tasks you need to complete.

Each of the next $n$ lines contains a single integer $t$ ( $0 \le t \le 2$ ). These are the tasks, in order. Each task is one of $0$ (nail), $1$ (screw), or $2$ (bolt).

출력

Output a single integer, which is the maximum number of tasks that can be completed.

예제2

예제 1
입력
```
10
1
1
1
0
0
0
0
2
2
2
```
예상 출력
```
10
```
예제 2
입력
```
10
0
1
2
0
1
2
0
1
2
0
```
예상 출력
```
5
```