The Fair Nut lives in n story house. a_i people live on the i-th floor of the house. Every person uses elevator twice a day: to get from the floor where he/she lives to the ground (first) floor and to get from the first floor to the floor where he/she lives, when he/she comes back home in the evening. 

It was decided that elevator, when it is not used, will stay on the x-th floor, but x hasn't been chosen yet. When a person needs to get from floor a to floor b, elevator follows the simple algorithm: 

  * Moves from the x-th floor (initially it stays on the x-th floor) to the a-th and takes the passenger. 
  * Moves from the a-th floor to the b-th floor and lets out the passenger (if a equals b, elevator just opens and closes the doors, but still comes to the floor from the x-th floor). 
  * Moves from the b-th floor back to the x-th. 

The elevator never transposes more than one person and always goes back to the floor x before transposing a next passenger. The elevator spends one unit of electricity to move between neighboring floors. So moving from the a-th floor to the b-th floor requires |a - b| units of electricity.

Your task is to help Nut to find the minimum number of electricity units, that it would be enough for one day, by choosing an optimal the x-th floor. Don't forget than elevator initially stays on the x-th floor. 

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the number of floors.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 100) — the number of people on each floor.

Output

In a single line, print the answer to the problem — the minimum number of electricity units.

Examples

Input

3
0 2 1


Output

16

Input

2
1 1


Output

4

Note

In the first example, the answer can be achieved by choosing the second floor as the x-th floor. Each person from the second floor (there are two of them) would spend 4 units of electricity per day (2 to get down and 2 to get up), and one person from the third would spend 8 units of electricity per day (4 to get down and 4 to get up). 4 ⋅ 2 + 8 ⋅ 1 = 16.

In the second example, the answer can be achieved by choosing the first floor as the x-th floor.
/**
 * Created by Aminul on 5/19/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Toph___A_Very_Toph_Problem_bitset_random {
    static int BLOCK_SIZE, f[], count[], a[], max, min;
    public static void main(String[] args)throws Exception {
        PrintWriter pw = new PrintWriter(System.out);


        int N = (int)1e5;
        Random random = new Random(46544674646L);
        long start = System.currentTimeMillis();

        int n = N, q = N; BLOCK_SIZE = (int)sqrt(n);
        a = new int[n+1];

        for(int i = 1; i <= n; i++){
            a[i] = random.nextInt(N)+1;
        }

        Node [] pair = new Node[q];

        for(int i = 0; i < q; i++){
            int u = random.nextInt(n)+1, v = random.nextInt(n)+1;
            if(u > v){int tmp = u; u = v; v = tmp;}
            pair[i] = new Node(u, v, i);
        }
        Arrays.sort(pair);

        int [] ans = new int[q];

        int maxN = (int)1e5;
        count = new int[maxN+1];
        f = new int[maxN+1];
        bitSet = new BitSet(maxN+1);

        int l = 1, r = 0, x = 0;
        max = 1;
        min = n;

        for(int i = 0; i < q; i++){
            while( r < pair[i].v){
                r++;x = a[r];
                add(x);
            }

            while( r > pair[i].v){
                x = a[r];
                remove(x);
                r--;
            }


            while( l > pair[i].u){
                l--;x = a[l];
                add(x);
            }

            while( l < pair[i].u){
                x = a[l];
                remove(x);
                l++;
            }


            ans[pair[i].idx] = bitSet.previousSetBit(n) - bitSet.nextSetBit(0);
        }

      //  for(int i: ans) pw.println(i);
        pw.close();

        debug(System.currentTimeMillis() - start);

    }

    static BitSet bitSet;

    static void add(int x){
        if(count[x] > 0) {
            f[count[x]]--;
            if (f[count[x]] == 0) bitSet.clear(count[x]);
        }
        count[x]++;
        if(count[x] > 0) {
            f[count[x]]++;
            if (f[count[x]] == 1) bitSet.set(count[x]);
        }
    }

    static void remove(int x){
        if(count[x] > 0) {
            f[count[x]]--;
            if (f[count[x]] == 0) bitSet.clear(count[x]);
        }
        count[x]--;
        if(count[x] > 0) {
            f[count[x]]++;
            if (f[count[x]] == 1) bitSet.set(count[x]);
        }
    }


    static class Node implements Comparable<Node>{
        public int u, v, idx;
        long order;
        public Node(int uu, int vv, int i){
            u = uu; v = vv; idx = i;
            order = hilbertOrder(u, v, 21, 0);
        }
        public int compareTo(Node n){
            return Long.compare(order, n.order);
        }
    }

    static int rotateDelta[] = {3, 0, 0, 1};
    static long hilbertOrder(int x, int y, int pow, int rotate) {
        if (pow == 0) {
            return 0;
        }
        int hpow = 1 << (pow-1);
        int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
        seg = (seg + rotate) & 3;

        int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
        int nrot = (rotate + rotateDelta[seg]) & 3;
        long subSquareSize = (1l) << (2*pow - 2);
        long ans = seg * subSquareSize;
        long add = hilbertOrder(nx, ny, pow-1, nrot);
        ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
        return ans;
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}