MCIPC Contest 2 P2 - Icicles

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

As part of your mandatory forty hours of community service, you have been tasked with getting rid of some rather unsightly icicles outside of Martingrove.

There are N icicles that you were tasked with destroying, with the i^\text{th} icicle having a length of L_i. When you destroy an icicle its length is set to 0. After careful examination, you realize that the icicles can be spared for aesthetic reasons if they are symmetrical. That is, a sequence of N icicles is considered symmetrical if the i^\text{th} icicle from the left has the same length as the i^\text{th} icicle from the right.

What is the minimum number of icicles that you must destroy?

Constraints

1 \le N, L_i \le 10^6

Input Specification

The first line contains the integer N.

The second line contains N integers, where the i^\text{th} integer represents the length of the i^\text{th} icicle.

Output Specification

Output a single integer, the minimum number of icicles needed to be destroyed.

Sample Input

5
3 2 1 4 3

Sample Output

2

Explanation for Sample

By destroying the 2^\text{nd} and 4^\text{th} icicles, the icicles are now symmetrical.


Comments

There are no comments at the moment.