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.BufferedWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
import java.util.Arrays;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.util.Comparator;

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

class Task253Div1C {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n=in.readInt();
        long ret=0;
        IntList list=new IntArrayList();
        for (int i=0; i<n; i++) {
            int x=in.readInt();
            while (list.size()>1 && list.back()<=Math.min(list.get(list.size()-2), x)) {
                list.popBack();
                ret+=Math.min(x, list.back());
            }
            list.add(x);
        }
        int[] arr=list.toArray();
        int pos= ArrayUtils.maxPosition(arr);
        n=arr.length;
        if (pos==0) pos++;
        if (pos==n-1) pos--;
        for (int l=pos-1, r=pos+1; n>2; n--) {
            ret+=Math.min(arr[l], arr[r]);
            if (l==0) pos=r++;
            else if (r==arr.length-1) pos=l--;
            else if (arr[l]>=arr[r]) pos=l--;
            else pos=r++;
        }
        out.printLine(ret);
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public void close() {
        writer.close();
    }

    public void printLine(long i) {
        writer.println(i);
    }

}

abstract class IntList extends IntCollection implements Comparable<IntList> {

    public abstract int get(int index);

    public IntIterator iterator() {
        return new IntIterator() {
            private int size = size();
            private int index = 0;

            public int value() throws NoSuchElementException {
                if (!isValid())
                    throw new NoSuchElementException();
                return get(index);
            }

            public void advance() throws NoSuchElementException {
                if (!isValid())
                    throw new NoSuchElementException();
                index++;
            }

            public boolean isValid() {
                return index < size;
            }
        };
    }

    public int back() {
        return get(size() - 1);
    }

    public int popBack() {
        throw new UnsupportedOperationException();
    }

    public int hashCode() {
        int hashCode = 1;
        for (IntIterator i = iterator(); i.isValid(); i.advance())
            hashCode = 31 * hashCode + i.value();
        return hashCode;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof IntList))
            return false;
        IntList list = (IntList)obj;
        if (list.size() != size())
            return false;
        IntIterator i = iterator();
        IntIterator j = list.iterator();
        while (i.isValid()) {
            if (i.value() != j.value())
                return false;
            i.advance();
            j.advance();
        }
        return true;
    }

    public int compareTo(IntList o) {
        IntIterator i = iterator();
        IntIterator j = o.iterator();
        while (true) {
            if (i.isValid()) {
                if (j.isValid()) {
                    if (i.value() != j.value()) {
                        if (i.value() < j.value())
                            return -1;
                        else
                            return 1;
                    }
                } else
                    return 1;
            } else {
                if (j.isValid())
                    return -1;
                else
                    return 0;
            }
            i.advance();
            j.advance();
        }
    }

}

class IntArrayList extends IntList {
    private int[] array;
    private int size;

    public IntArrayList() {
        this(10);
    }

    public IntArrayList(int capacity) {
        array = new int[capacity];
    }

    public int get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException();
        return array[index];
    }

    public int size() {
        return size;
    }

    public void add(int value) {
        ensureCapacity(size + 1);
        array[size++] = value;
    }

    public void ensureCapacity(int newCapacity) {
        if (newCapacity > array.length) {
            int[] newArray = new int[Math.max(newCapacity, array.length << 1)];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

    public int[] toArray() {
        int[] array = new int[size];
        System.arraycopy(this.array, 0, array, 0, size);
        return array;
    }

    public int popBack() {
        return array[--size];
    }
}

abstract class IntCollection {
    public abstract IntIterator iterator();
    public abstract int size();
    public abstract void add(int value);

    public int[] toArray() {
        int size = size();
        int[] array = new int[size];
        int i = 0;
        for (IntIterator iterator = iterator(); iterator.isValid(); iterator.advance())
            array[i++] = iterator.value();
        return array;
    }

}

class ArrayUtils {

    public static int maxPosition(int[] array) {
        return maxPosition(array, 0, array.length);
    }

    public static int maxPosition(int[] array, int from, int to) {
        if (from >= to)
            return -1;
        int max = array[from];
        int result = from;
        for (int i = from + 1; i < to; i++) {
            if (array[i] > max) {
                max = array[i];
                result = i;
            }
        }
        return result;
    }

}

interface IntIterator {
    public int value() throws NoSuchElementException;
    /*
     * @throws NoSuchElementException only if iterator already invalid
     */
    public void advance() throws NoSuchElementException;
    public boolean isValid();
}
