You are given an array ~a~ of length ~n~. You may repeatedly perform the following operation:

• Choose an index ~i~ such that ~i + 3 \le |a|~ (where ~|a|~ is the current array length), and ~a_i = a_{i+1} = a_{i+2} = a_{i+3} = i~.
• Delete these four elements.

After a deletion, the remaining elements are re-indexed from ~1~ to ~|a|~.

Find the minimum possible final length of the array if you apply operations in an optimal order.

Input

The first line contains a single integer ~n~ ~(1 \le n \le 2 \times 10^5)~.

The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9)~.

Output

Print one integer: the minimum possible length of the array after performing the operation on indices in the optimal ordering.

Example 1

Input

8
1 1 1 1 1 2 3 4

Output

4

Explanation

Delete the first four elements (~i=1~). The remaining array is ~[1,2,3,4]~, so no further deletion is possible.

Example 2

Input

12
1 1 1 1 5 5 5 5 5 5 5 5

Output

0

Explanation

One optimal sequence is:

1. Delete the block at indices ~5..8~.
2. The last four ~5~'s shift to indices ~5..8~, so delete them.
3. The four ~1~'s remain at indices ~1..4~, so delete them.

The array becomes empty.

Example 3

Input

11
1 1 3 3 3 3 1 1 1 1 1

Output

3

Explanation

Delete the four ~3~'s at indices ~3..6~. The remaining seven elements are all ~1~, so one more deletion can be performed at index ~1~, leaving three elements.