static long solve(int[] input) {
        int n = input.length;
        long[][] dp = new long[n][2];
        dp[0][0] = input[0];
        dp[0][1] = -input[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Long.MIN_VALUE;
            dp[i][1] = Long.MAX_VALUE;
            long sum = 0;
            for (int j = i; j >= Math.max(0, i - 2); j--) {
                sum += input[j];
                if (j - 1 >= 0) {
                    dp[i][0] = Math.max(dp[i][0], dp[j - 1][1] + sum);
                } else {
                    dp[i][0] = Math.max(dp[i][0], sum);
                }
            }
            sum = 0;
            for (int j = i; j >= Math.max(0, i - 2); j--) {
                sum -= input[j];
                if (j - 1 >= 0) {
                    dp[i][1] = Math.min(dp[i][1], dp[j - 1][0] + sum);
                } else {
                    dp[i][1] = Math.min(dp[i][1], sum);
                }
            }
        }
        return dp[n - 1][0];
    }