Misha has an array of n integers indexed by integers from 1 to n. Let's define palindrome degree of array a as the number of such index pairs (l, r)(1 ≤ l ≤ r ≤ n), that the elements from the l-th to the r-th one inclusive can be rearranged in such a way that the whole array will be a palindrome. In other words, pair (l, r) should meet the condition that after some rearranging of numbers on positions from l to r, inclusive (it is allowed not to rearrange the numbers at all), for any 1 ≤ i ≤ n following condition holds: a[i] = a[n - i + 1]. 

Your task is to find the palindrome degree of Misha's array.

Input

The first line contains integer n (1 ≤ n ≤ 105).

The second line contains n positive integers a[i] (1 ≤ a[i] ≤ n), separated by spaces — the elements of Misha's array.

Output

In a single line print the answer to the problem.

Examples

Input

3
2 2 2


Output

6


Input

6
3 6 5 3 3 5


Output

0


Input

5
5 5 2 5 2


Output

4

Note

In the first sample test any possible pair (l, r) meets the condition.

In the third sample test following pairs (1, 3), (1, 4), (1, 5), (2, 5) meet the condition.
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class MishaandPalindromeDegree {
        private static int N;
    private static int[] seq, count, leftLocked, rightLocked;
        
    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer tk;

        N = in(br.readLine());
        seq = new int[N];
        count = new int[N];
        leftLocked = new int[N];
        rightLocked = new int[N];
        tk = mkst(br);
        for (int i = 0; i < N; ++i) {
            int num = in(tk) - 1;
            seq[i] = num;
        }
        for (int i = 0; i < N; ++i) {
            count[seq[i]]++;
        }

        int middleVal = -1, middleLoc = N / 2;
        for (int i = 0; i < N; ++i) {
            if ((count[i] & 1) == 1) {
                if (middleVal == -1) {
                    middleVal = i;
                } else {
                    middleVal = -2;
                    break;
                }
            }
        }

        if (middleVal == -2) {
            pw.println("0");
        } else {
            long total = 0;

            int beg = 0, end = N - 1;

            while (end > beg && !(middleVal >= 0 && end <= middleLoc && seq[middleLoc] != middleVal)) {
                int val = seq[end];
                int endalt = N - end - 1;
                int lockoff = 0;

                if (endalt == end) {

                } else if (endalt < end) {
                    lockoff = 1;
                } else if (seq[endalt] == val) {
                    lockoff = -1;
                } else {
                    break;
                }
                count[val]--;
                rightLocked[val] += lockoff;

                if (count[val] < rightLocked[val] + leftLocked[val] + (val == middleVal && end > N / 2 ? 1 : 0)) {
                    count[val]++;
                    rightLocked[val] -= lockoff;

                    break;
                }
                end--;
            }

            while (beg < N && end < N && !(middleVal >= 0 && beg >= middleLoc && seq[middleLoc] != middleVal)) {
                total += N - end;

                int begval = seq[beg], begalt = N - beg - 1, minend = -1;
                count[begval]--;
                if (begalt == beg) {

                } else if (beg < begalt && begalt <= end) {
                    leftLocked[begval]++;
                } else if (seq[begalt] == begval) {
                    rightLocked[begval]--;
                } else {
                    minend = begalt;
                    leftLocked[begval]++;
                }

                while (end < N - 1
                        && (count[begval] < rightLocked[begval] + leftLocked[begval]
                                + (begval == middleVal && beg < middleLoc && middleLoc <= end ? 1 : 0)
                                || end < minend || end <= beg)) {
                    end++;

                    int endalt = N - end - 1, endval = seq[end];
                    if (endalt == end) {

                    } else if (!(beg < endalt && endalt <= end) && seq[endalt] == endval) {
                            leftLocked[endval]++;
                    } else {
                        rightLocked[endval]--;
                    }

                    count[endval]++;
                }

                if (count[begval] < rightLocked[begval] + leftLocked[begval]
                        + (begval == middleVal && beg < middleLoc && middleLoc <= end ? 1 : 0)) {
                    break;
                }
                beg++;
            }

            pw.println(total);
        }

        br.close();
        pw.close();
        System.exit(0);
    }

    public static StringTokenizer mkst(BufferedReader br) throws IOException {
        return new StringTokenizer(br.readLine());
    }

    public static int in(StringTokenizer tk) throws IOException, NumberFormatException {
        return Integer.parseInt(tk.nextToken());
    }

    public static int in(String s) throws NumberFormatException {
        return Integer.parseInt(s);
    }

    public static long ln(StringTokenizer tk) throws IOException, NumberFormatException {
        return Long.parseLong(tk.nextToken());
    }

    public static long ln(String s) throws NumberFormatException {
        return Long.parseLong(s);
    }

    public static double db(StringTokenizer tk) throws IOException, NumberFormatException {
        return Double.parseDouble(tk.nextToken());
    }

    public static double db(String s) throws NumberFormatException {
        return Double.parseDouble(s);
    }
}
