描述

给定一个长度为 N 的整数序列 A = (A₁, A₂, …, Aₙ)。你可以执行若干次（可以为零次）如下操作：

选择一个整数 k（1 ≤ k ≤ |A|−3），使得 Aₖ = Aₖ₊₁ = Aₖ₊₂ = Aₖ₊₃，然后将这四个元素从序列中删除（即用剩余部分拼接形成新序列）。

求经过任意次操作后，序列的最小可能长度。

输入输出格式

输入

第一行一个整数 N，表示序列长度。 第二行 N 个整数 A₁, A₂, …, Aₙ，表示原始序列。

输出

输出一个整数，表示最终序列的最小可能长度。

样例

10
1 1 1 4 4 4 4 1 2 3

2

限制

• 1 ≤ N ≤ 2×10⁵
• 1 ≤ Aᵢ ≤ N
• 所有输入均为整数