Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

* 2 \leq N \leq 2\times 10^5
* |A_i|\leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 ... A_N


Output

Print the maximum possible sum of the chosen elements.

Examples

Input

6
1 2 3 4 5 6


Output

12


Input

5
-1000 -100 -10 0 10


Output

0


Input

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000


Output

5000000000


Input

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49


Output

295
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static class Task {

        private int n;
        private long[] arr;
        private Map<Long, Long> memo;

        private long getAns(int from) {
            long sum1 = 0;
            long sum2 = 0;
            for (int i = from; i < n; i+=2) {
                sum1 += arr[i];
            }

            for (int i = from + 1; i < n; i+=2) {
                sum2 += arr[i];
            }

            return Math.max(sum1, sum2);
        }

        private long dp(int idx, int k) {
            if (k == 0) {
                return 0;
            }

            if (idx >= n) {
                return Long.MIN_VALUE;
            }

            if (n - idx + 1 < 2 * k) {
                return Long.MIN_VALUE;
            }

            long key = (long) k * n + idx;
            if (memo.containsKey(key)) {
                return memo.get(key);
            }

//            if ((n - idx) % 2 == 0) {
//                return getAns(idx);
//            }

            long chooseRes = arr[idx] + dp(idx + 2, k - 1);
            long nonChooseRes = dp(idx + 1, k);
            long res = Math.max(chooseRes, nonChooseRes);
            memo.put(key, res);
            return res;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextLong();
            }

//            memo = new Long[n + 1];
            memo = new HashMap<>();
            long ans = dp(0, n / 2);
            out.println(ans);
//            if (n % 2 == 0) {
//                long sum1 = 0;
//                long sum2 = 0;
//                for (int i = 0; i < n; i+=2) {
//                    sum1 += arr[i];
//                }
//
//                for (int i = 1; i < n; i+=2) {
//                    sum2 += arr[i];
//                }
//
//                ans = Math.max(sum1, sum2);
//            } else {
//
//            }
        }
    }

    private static void sort(double[] arr) {
        Double[] objArr = Arrays.stream(arr).boxed().toArray(Double[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void sort(int[] arr) {
        Integer[] objArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void sort(long[] arr) {
        Long[] objArr = Arrays.stream(arr).boxed().toArray(Long[]::new);
        Arrays.sort(objArr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = objArr[i];
        }
    }

    private static void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(1, in, out);
        out.close();
    }

    public static void main(String[] args) {
        new Thread(null, () -> solve(), "1", 1 << 26).start();
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

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

    }

}