#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1001;
int n, dp[mxN][mxN];
// #define MAX_N 1000
// #define MAX_Q 10000
// #define MAX_VALUE 1000000000
// static int secret_count;
// int Secret(int X, int Y) {
// ++secret_count;
// if (!(0 <= X && X <= MAX_VALUE)) {
// fprintf(stderr, "Wrong Answer [1]\n");
// exit(0);
// }
// if (!(0 <= Y && Y <= MAX_VALUE)) {
// fprintf(stderr, "Wrong Answer [1]\n");
// exit(0);
// }
// return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
// }
void divi(int l, int r) {
if (l >= r) return;
int m = (l + r) >> 1;
for (int i = m - 1; i >= l; i--) dp[i][m] = Secret(dp[i + 1][m], dp[i][i]);
for (int i = m + 2; i <= r; i++) dp[m + 1][i] = Secret(dp[m + 1][i - 1], dp[i][i]);
divi(l, m);
divi(m + 1, r);
}
void Init(int N, int A[]) {
memset(dp, -1, sizeof dp);
for (int i = 0; i < N; i++) dp[i][i] = A[i];
divi(0, N - 1);
}
int Query(int L, int R) {
if (dp[L][R] != -1) return dp[L][R];
for (int i = L; i < R; i++)
if (dp[L][i] != -1 && dp[i + 1][R] != -1) return Secret(dp[L][i], dp[i + 1][R]);
assert(0);
}
// int main() {
// int A[] = { 1, 4, 7, 2, 5, 8, 3, 6 };
// Init(8, A);
// cout << Query(0, 3) << '\n';
// cout << Query(1, 7) << '\n';
// cout << Query(5, 5) << '\n';
// cout << Query(2, 4) << '\n';
// }
