Secret

#include <bits/stdc++.h>
#define f first
#define s second
#define N 1234
#define mid ((a + b)/2)
#include "secret.h"
using namespace std;
typedef pair<int, int> pii;

int v[N], tree[4*N], inutil, n, ans[N][N], ini[N];

map<pii, int> dp;

int S(int a, int b)
{
	if(dp[pii(a, b)] != 0) return dp[pii(a, b)];

	return dp[pii(a, b)] = dp[pii(b, a)] = Secret(a, b);
}

void build(int nod, int a, int b)
{
	if(b - a <= 1) return;

  for (int i = mid - 1; i >= a; --i)
  		if(ans[i][mid] == -1) ans[i][mid] = S(ans[i][i + 1], ans[i + 1][mid]);

  for (int i = mid + 1; i <= b; ++i)
  	    if(ans[mid][i] == -1) ans[mid][i] = S(ans[mid][i - 1], ans[i - 1][i]);

	build(2*nod, a, mid), build(2*nod + 1, mid, b);
}

int Query(int l, int r)
{
	if(r < l) swap(l, r);

	for(int i = l + 1; i <= r; i++)
	{
		if(ans[l][i] != -1 && ans[i][r + 1] != -1) return S(ans[l][i], ans[i][r + 1]);
	}

	return ans[l][r + 1];
}

void Init(int n_, int A[])
{
    n = n_;

    memset(ans, -1, sizeof ans);

	for(int i = 0; i < n; i++) v[i] = A[i], ans[i][i + 1] = v[i];

	build(1, 0, n);
}