Single-letter palindrome#3031
Recently, the computer game development company Gold&Silver Software released a new smartphone game called Single-letter Palindrome. The game's simplicity quickly made it popular.
The game begins with the player being given a string consisting of characters. The objective is to transform this string into a single-letter palindrome using a certain number of moves. In each move, the player can swap two adjacent characters in the string.
Figure 1. Examples of single-letter palindromes.
A string is considered a single-letter palindrome if there exists a natural number (1 \leq i \leq N) such that S_i = S'_i, where S'_1 = S_N, S'_2 = S_{N-1}, ..., S'_N = S_1. The string S' is called the reverse of the string .
Figure 2. Description of the second example, a sequence of two moves.
For a given string , determine the minimum number of moves necessary to obtain a single-letter palindrome.
The first line of the input contains a single integer (2 \leq N \leq 250000).
The second line contains integers separated by single spaces, each between and . Each integer represents the code of the corresponding character in the string. Characters are considered equal if their codes are equal.
Output a single number — the minimum number of moves needed to transform the given string into a single-letter palindrome. It is guaranteed that a solution exists.
Example 1