Genome Evolution

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N(3001);

int A[N], B[N], hash[N], hash2[N];
ll AA[N], BB[N], AAA[N], BBB[N];
vector<ll> U, V;

int prob(int n){
    for(int i = 1; i <= n; ++i){
        scanf("%d", &A[i]);
        AA[i] = hash[A[i]];
        AA[i] += AA[i - 1];
        AAA[i] = hash2[A[i]];
        AAA[i] += AAA[i - 1];
    }
    for(int i = 1; i <= n; ++i){
        scanf("%d", &B[i]);
        BB[i] = hash[B[i]];
        BB[i] += BB[i - 1];
        BBB[i] = hash2[B[i]];
        BBB[i] += BBB[i - 1];
    }
    int cnt = 0;
    for(int i = 2; i <= n; ++i){
        U.clear();
        V.clear();
        for(int j = 1; j <= n - i + 1; ++j){
            U.push_back(BB[i + j - 1] - BB[j - 1]);
            V.push_back(BBB[i + j - 1] - BBB[j - 1]);
        }
        sort(U.begin(), U.end());
        sort(V.begin(), V.end());
        for(int j = 1; j <= n - i + 1; ++j){
            vector<ll>::iterator x = lower_bound(U.begin(), U.end(), AA[i + j - 1] - AA[j - 1]);
            vector<ll>::iterator y = lower_bound(V.begin(), V.end(), AAA[i + j - 1] - AAA[j - 1]);
            if(x != U.end() and *x == AA[i + j - 1] - AA[j - 1] and
                y != V.end() and *y == AAA[i + j - 1] - AAA[j - 1]) cnt++;
        }
    }
    return cnt;
}

int main(){
    srand(97);
    int n;
    for(int i = 0; i < N; ++i) hash[i] = rand();
    for(int i = 0; i < N; ++i) hash2[i] = rand();
    while(true){
        scanf("%d", &n);
        if(n == 0) break;
        printf("%d\n", prob(n));
    }
    return 0;
}