#include <bits/stdc++.h>

using namespace std;

extern int count_pair(int, int, int);
extern int find_character(int, std::vector<int>);
//
//extern int guess_palindromicity(int);
//int count_pair(int, int, int);
//int find_character(int, std::vector<int>);
//std::vector<std::vector<int>> shuffle(std::vector<std::vector<int>>) ;
//
//static int N, cnt1, cnt2;
//static int S[5002];
//
//void assertion(bool x, std::string msg) {
//    if (x) return;
//    printf("Wrong : %s", msg.c_str());
//    exit(0);
//}
//
//int count_pair(int x, int y, int z) {
//    ++cnt1;
//    assertion(x != y && y != z && x != z, "Invalid Query c1");
//    assertion(0 <= x && 0 <= y && 0 <= z &&
//            x < N && y < N && z < N, "Invalid Query c2");
//
//    int ret = 0;
//    if(S[x] == S[y]) ++ret;
//    if(S[y] == S[z]) ++ret;
//    if(S[z] == S[x]) ++ret;
//
//    return ret;
//}
//
//int find_character(int x, std::vector<int> Y) {
//    ++cnt2;
//    assertion(0 <= x && x < N, "Invalid Query f");
//    for(int y : Y) {
//        assertion(0 <= y && y < N, "Invalid Query f");
//    }
//    for(int y : Y) {
//        if(S[x] == S[y]) return 1;
//    }
//    return 0;
//}

int guess_palindromicity(int n){
    vector <int> n1, n2;

    for (int i = 1; i < n / 2; ++ i){
        int gg = count_pair(0, i, n - 1 - i);
        if (!gg) return 0;
        if (gg == 1) n1.push_back(i);
        else n2.push_back(i);
    }

    //cout << n1.back() << endl;

    vector <int> dhs = n1;
    for (int i : n1) dhs.push_back(n - i - 1);

    if (find_character(0, dhs)) return 0;

    if (n2.size()){
        int i = n2.back();
        if (count_pair(n - 1, n - 1 - i, i) == 1) return 0;
        return 1;
    }
    int i = n1.back();
    int gg = count_pair(0, n - 1, i);
    if (!gg) return 0;
    if (gg == 3) return 1;
    if (count_pair(n - 1, i, n - i - 1) == 3) return 0;
    return 1;
}
//
//void solve() {
//    assertion(scanf("%d", &N) == 1, "Wrong Input");
//    for(int i=0;i<N;i++) assertion(scanf("%d", &S[i]) == 1, "Wrong Input");
//    for(int i=0;i<N;i++) assertion(1 <= S[i] && S[i] <= 5000, "Wrong Input");
//
//    cnt1 = 0, cnt2 = 0;
//
//    int res = guess_palindromicity(N);
//    //cout << res << endl;
//    int ans = 1;
//    for(int i=0;i<N/2;i++) if(S[i] != S[N-1-i]) ans = 0;
//
//    assertion(res == ans, "Wrong Guess");
//    printf("Correct: %d %d", cnt1, cnt2);
//}
//
//int main(){
//    int t = 1;
//    while (t --) solve();
//}