Everything Is A Nail
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.
|Sample Input 1||Sample Output 1|
10 1 1 1 0 0 0 0 2 2 2
|Sample Input 2||Sample Output 2|
10 0 1 2 0 1 2 0 1 2 0