Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn't have an adjacent number to the left or right, Artem doesn't get any points. 

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai (1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Examples

Input

5
3 1 5 2 6


Output

11


Input

5
1 2 3 4 5


Output

6


Input

5
1 100 101 100 1


Output

102
9
72 49 39 50 68 35 75 94 56
 4
2 3 1 2
 8
3 4 3 1 1 3 4 1
 1
4
 7
2 1 2 2 2 2 2
 6
1 7 3 1 6 2
 8
77 84 26 34 17 56 76 3
 2
93 51
 1
87
 4
86 21 58 60
 10
96 66 8 18 30 48 34 11 37 42
 6
46 30 38 9 65 23
 5
21 6 54 69 32
 3
1 2 1
 3
31 19 5
 10
4 2 2 4 1 2 2 4 2 1
 7
82 60 92 4 2 13 15
 9
4 5 2 2 3 1 3 3 5
 5
2 6 2 1 2
 2
3 1

435 4 15 0 10 12 279 0 0 118 299 145 74 1 5 21 129 23 6 0
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.PrintStream;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    class Pair implements Comparable<Pair>{
        int id;
        int l;
        int r;
        Pair next;
        Pair prev;

        Pair(int id, int l, int r, Pair prev) {
            this.id = id;
            this.l = l;
            this.r = r;
            this.prev = prev;
        }

        public int compareTo(Pair o) {
            return Math.min(o.r, o.l) - Math.min(this.r, this.l);
        }
    }
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.ni();
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.ni();
        }

        if(n < 3) {
            out.println(0);
            return;
        }
        BinaryHeapWithIncreasePriority<Pair> pairs = new BinaryHeapWithIncreasePriority<Pair>(n);
        Pair prev = new Pair(0, a[0], a[2], null);
        pairs.add(0, prev);
        for (int i = 1; i < n-2; i++) {
            Pair pair = new Pair(i, a[i], a[i + 2], prev);
            pairs.add(i, pair);
            prev.next = pair;
        }
        long ans = 0;
        while(!pairs.isEmpty()) {
            Pair maxPair = pairs.remove();
            ans += Math.min(maxPair.l, maxPair.r);
            if(maxPair.prev != null) {
                prev = maxPair.prev;
                pairs.remove(prev.id);
                prev.r = maxPair.r;
                pairs.add(prev.id, prev);
                prev.next = maxPair.next;
            }
            if(maxPair.next != null) {
                Pair next = maxPair.next;
                next.l = maxPair.l;
                pairs.remove(next.id);
                pairs.add(next.id, next);
                next.prev = maxPair.prev;
            }
        }
        out.println(ans);
    }
}

class InputReader  extends BufferedReader {
    public InputReader(InputStream st) {
        super(new InputStreamReader(st));
    }

    public int nextInt() {
        try {
            int c = read();

            while (isWhiteSpace(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int ret = 0;
            while (c >= 0 && !isWhiteSpace(c)) {
                if (c < '0' || c > '9') {
                    throw new RuntimeException();
                }
                ret = ret * 10 + c - '0';
                c = read();
            }
            return ret * sgn;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public int ni() {
        return nextInt();
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }


    static boolean isWhiteSpace(int c) {
        return c >= 0 && c <= 32;
    }



}

class BinaryHeapWithIncreasePriority<E extends Comparable<E>> {
    Comparable[] h;
    int[] pos2Id;
    int[] id2Pos;
    int size;

    public BinaryHeapWithIncreasePriority(int maxSize) {
        h = new Comparable[maxSize];
        pos2Id = new int[maxSize];
        id2Pos = new int[maxSize];
        Arrays.fill(id2Pos, -1);
        size = 0;
    }

    public void add(int id, E node) {
        h[size] = node;
        pos2Id[size] = id;
        id2Pos[id] = size;
        moveUp(size++);
    }

    public E remove(int minId) {
        int pos = id2Pos[minId];
        if(pos == -1) {
            return null;//no such element
        }
        E removedNode = (E) h[pos];
        E lastNode = (E) h[--size];
        id2Pos[minId] = -1;
        h[size] = null;

        if (size != pos && size > 0) {
            h[pos] = lastNode;
            int id = pos2Id[size];
            id2Pos[id] = pos;
            pos2Id[pos] = id;
            moveDown(pos);
            if(id2Pos[id] == pos) {
                moveUp(pos);
            }
        }
        return removedNode;
    }


    void swap(int i, int j) {
        Comparable x = h[i];
        h[i] = h[j];
        h[j] = x;
        int t = pos2Id[i];
        pos2Id[i] = pos2Id[j];
        pos2Id[j] = t;
        id2Pos[pos2Id[i]] = i;
        id2Pos[pos2Id[j]] = j;
    }

    void moveUp(int pos) {
        while (pos > 0) {
            int parent = (pos - 1) >> 1;
            if (h[pos].compareTo(h[parent]) >= 0) {
                break;
            }
            swap(pos, parent);
            pos = parent;
        }
    }

    public E remove() {
        E removedNode = (E) h[0];
        int minId = pos2Id[0];
        id2Pos[minId] = -1;
        Comparable lastNode = h[--size];
        h[size] = null;
        if (size > 0) {
            h[0] = lastNode;
            int id = pos2Id[size];
            id2Pos[id] = 0;
            pos2Id[0] = id;
            moveDown(0);
        }
        return removedNode;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    void moveDown(int pos) {
        while (pos < size / 2) {
            int child = 2 * pos + 1;
            if (child < size - 1 && h[child].compareTo(h[child + 1]) > 0) {
                ++child;
            }
            if (h[pos].compareTo(h[child]) <= 0) {
                break;
            }
            swap(pos, child);
            pos = child;
        }
    }

}
