Single-letter palindrome

Recently, the computer game development company "GoldSilver Software" released a new smartphone game called "Single-letter Palindrome." The game's simplicity has quickly made it popular.

In the game, players start with a string (S), which consists of (N) characters in the player's native language. The objective is to transform this string into a single-letter palindrome using a series of moves. In each move, the player can swap two adjacent characters in the string.

*Figure 1. Examples of single-letter palindromes.*

A string (S) is considered a single-letter palindrome if there exists a natural number (i), where (1 $\le$ i $\le$ 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 referred to as the "reverse" of the string (S).

*Figure 2. Description of the second example, a sequence of two moves.*

For a given string (S), you need to determine the minimum number of moves required to transform it into a single-letter palindrome.

Input

The first line of the input file contains a single integer (N) ((2 $\le$ N $\le$ 250000)).

The second line of the input file describes the string (S) and contains (N) integers ranging from (1) to (65535), separated by single spaces. Each number represents the code of the corresponding character in the string. Characters are considered equal if their corresponding codes are equal.

Output

The output file should contain a single number—the minimum number of moves required to transform the given string (S) into a single-letter palindrome. It is guaranteed that a solution exists.

Examples