problem

There is one bar-shaped candy with a length of N mm (where N is an even number). Two JOI officials decided to cut this candy into multiple pieces and divide them into a total of N / 2 mm. did.

For unknown reasons, this candy has different ease of cutting depending on the location. The two examined the candy every millimeter from the left and figured out how many seconds it would take to cut at each location. .2 Create a program that finds the minimum number of seconds it takes for a person to cut a candy.

output

The output consists of one line containing the minimum number of seconds it takes for two people to cut the candy.

Input / output example

Input example 1


6
1
8
12
6
2


Output example 1


7


In this case, cutting 1 and 4 millimeters from the left edge minimizes the number of seconds. The number of seconds is 1 and 6 seconds, for a total of 7 seconds.

<image>

The above question sentences and the data used for the automatic referee are the question sentences created and published by the Japan Committee for Information Olympics and the test data for scoring.



input

The length of the bar N (2 ≤ N ≤ 10000, where N is an even number) is written on the first line of the input. On the first line of the input i + (1 ≤ i ≤ N − 1), An integer ti (1 ≤ ti ≤ 10000) is written to represent the number of seconds it takes to cut the i-millimeter location from the left edge. Note that there are N − 1 locations that can be cut.

Of the scoring data, the minimum value can be achieved by cutting at most 2 points for 5% of the points, and the minimum value can be achieved by cutting at most 3 points for 10%. For 20% of the points, N ≤ 20.

Example

Input

6
1
8
12
6
2


Output

7
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		IO io = new IO();
		int n = io.nextInt();
		int[] c = new int[n + 1];
		for (int i = 1; i < n; i++) {
			c[i] = io.nextInt();
		}
		c[n] = 0;
		int[][][] dp = new int[2][2][n / 2 + 1];
		int[] min0 = new int[n / 2 + 1];
		int[] min1 = new int[n + 1];
		Arrays.fill(min0, 1 << 29);
		Arrays.fill(min1, 1 << 29);
		for (int i=0;i<2;i++) {
			for(int j=0;j<2;j++) {
				Arrays.fill(dp[i][j], 1<<29);
			}
		}
		int bef = 0;
		int now = 1;
		int ans = 1 << 29;
		dp[1][0][0] = min1[0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n / 2; j++) {
				if (j > i) {
					continue;
				}
				dp[0][now][j] = min1[i - j] + c[i];
				dp[1][now][j] = min0[j] + c[i];
				min0[j] = Math.min(min0[j], dp[0][now][j]);
				min1[i - j] = Math.min(min1[i - j], dp[1][now][j]);
				if (j == n / 2) {
					ans = Math.min(ans,dp[0][now][j]);
				}else if(n-j+i == n/2) {
					ans = Math.min(ans,dp[1][now][j]);
				}
			}
			now = 1 - now;
			bef = 1 - bef;
		}
		System.out.println(ans);
	}

}

class IO {
	private final InputStream in;
	final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public IO() {
		this(System.in);
	}

	public IO(InputStream source) {
		this.in = source;
	}

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private static boolean isNewLine(int c) {
		return c == '\n' || c == '\r';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	private void skipNewLine() {
		while (hasNextByte() && isNewLine(buffer[ptr]))
			ptr++;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public boolean hasNextLine() {
		skipNewLine();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public char[] nextCharArray(int len) {
		char[] s = new char[len];
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		int i = 0;
		int b = readByte();
		while (isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}

	public String nextLine() {
		if (!hasNextLine()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (!isNewLine(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}

	public char nextChar() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		return (char) readByte();
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] arrayInt(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] arrayLong(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}

	public double[] arrayDouble(int n) {
		double[] a = new double[n];
		for (int i = 0; i < n; i++)
			a[i] = nextDouble();
		return a;
	}

	public void arrayInt(int[]... a) {
		for (int i = 0; i < a[0].length; i++)
			for (int j = 0; j < a.length; j++)
				a[j][i] = nextInt();
	}

	public int[][] matrixInt(int n, int m) {
		int[][] a = new int[n][m];
		for (int i = 0; i < n; i++)
			a[i] = arrayInt(m);
		return a;
	}

	public char[][] charMap(int n, int m) {
		char[][] a = new char[n][m];
		for (int i = 0; i < n; i++)
			a[i] = nextCharArray(m);
		return a;
	}
}