Army Training

Time limit2sMemory limit1024 MB

Summary

Given readiness scores (1 to 3) for n soldiers, find the fewest soldiers to raise to score 1 so that at least half of the army is fully ready.

Level: Easy1 of 10
Topics: Array, Implementation
Solved: No attempts yet

Statement

Before an attack, commanders must be confident of victory, so every soldier needs to be ready for anything. At the morning inspection, Katniss and Peeta rated the fighting strength of their army. For each soldier they wrote a number from 1 to 3 on a sheet of paper as that soldier's readiness: 1 means fully ready for battle, and 3 means the soldier cannot do anything. Katniss devised a tactic that guarantees victory if at least half of the soldiers are fully ready for battle. Looking at the sheet, she asks: what is the minimum number of soldiers that must still be fully trained so that her tactic guarantees the win? She has no time to think, so help her find this number.

Input

The first line contains the number of soldiers $n$ ( $1 \le n \le 100\,000$ ). The second line contains $n$ integers $a_i$ ( $1 \le a_i \le 3$ ), the readiness values written on the sheet.

Output

Print the minimum number of soldiers that must be made fully ready for battle so that at least half of the army is ready and victory is guaranteed.

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
1
```
Example 2
Input
```
3
1 1 2
```
Expected output
```
0
```