为什么这个暴力过不了第三个点

#include<bits/stdc++.h>
using namespace std;
int a[3009];
long long pre[3009];
long long mem[3009][3009];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        unsigned long long ans = 0;
        for(int i = 1;i <= n;i++){
            unsigned long long an= 0;
            long long maxx = -0x3f3f3f3f3f3f3f3f;
            for(int len = l;len <= r;len++){
                long long maxxx = -0x3f3f3f3f3f3f3f3f;
                if(mem[i][len] != 0){
                    maxxx = mem[i][len]; 
                    goto zxt;
                }
                for(int be = max(1,i - len + 1);be <= i && be + len - 1 <= n;be++){
                    maxxx = max(maxxx,pre[be + len - 1] - pre[be - 1]);
//                    cerr << i << ' ' << be + len - 1 << " " << be << ' ' << pre[be + len - 1] - pre[be - 1] << endl;
                }
                zxt:
                mem[i][len] = maxxx;
                maxx = max(maxx,maxxx);
            }
//            cerr << maxx << endl;
            maxx *= i;
            an += maxx;
            ans ^= an;
        }
        cout << ans << '\n';
    }
}