Maximum Independent Set in a Special Graph

You are given a positive integer sequence \(a\) of length \(n\) where each \(a_i \in \{1,2,3\}\) for \(1 \le i \le n\). Based on this sequence, construct an undirected graph with \(n\) nodes numbered from 1 to \(n\) using the following rules:

• If \(a_i = 1\), do nothing.
• If \(a_i = 2\), add an edge between node \(i\) and every node with a smaller index.
• If \(a_i = 3\), add an edge between node \(i\) and every node with a larger index.

An independent set is a set of nodes in which no two nodes are directly connected by an edge. Your task is to find the size of the maximum independent set in this graph.

Note on the Graph Construction:
For any two nodes \(i\) and \(j\) with \(i < j\), an edge exists between them if and only if \(a_i = 3\) or \(a_j = 2\).

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)).
2. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), each being 1, 2, or 3.

outputFormat

Output a single integer representing the size of the maximum independent set.

sample

4
2 1 1 3

4