AT_abc438_c [ABC438C] 1D puyopuyo

You are given an integer sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . You can perform the following operation zero or more times in any order: - Choose an integer $ k $ between $ 1 $ and $ |A|-3 $ , inclusive, such that $ A_k=A_{k+1}=A_{k+2}=A_{k+3} $ , and remove $ A_k,A_{k+1},A_{k+2},A_{k+3} $ from $ A $ . (More formally, replace $ A $ with $ (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N) $ .) Here, $ |A| $ represents the length of the integer sequence $ A $ . Find the minimum possible value of the final $ |A| $ after repeating the operation.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the minimum possible value of the final $ |A| $ after repeating the operation.

### Sample Explanation 1 You can make $ |A|=2 $ with two operations as follows: - Choose $ k=4 $ . This choice is valid since $ A_4=A_5=A_6=A_7=4 $ holds. $ A=(1,1,1,1,2,3) $ is obtained. - Choose $ k=1 $ . This choice is valid since $ A_1=A_2=A_3=A_4=1 $ holds. $ A=(2,3) $ is obtained. It is impossible to make $ |A| $ less than $ 2 $ , so output $ 2 $ . ### Sample Explanation 2 You cannot perform any operation from the beginning. ### Constraints - $ 1\le N\le 2\times 10^5 $ - $ 1\le A_i\le N $ - All input values are integers.