<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

429. Problem Stacks
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Fedor and Sergey are playing a game while preparing for the World Finals. They have chosen a lot of problems to solve, and arranged the problem statements into n heaps, with i-th heap containing ai problem statements, and put those heaps along one straight line. They make alternating moves, and each move consists of taking some (maybe all) problems from the first or from the last heap (but not from both) and solving them (and thus dumping the corresponding problem statements). When some player takes all problems from the first heap, the next heap is now considered first; when some player takes all problems from the last heap, the previous heap is now considered last. The player who doesn't have any more problems to solve loses.

Obviously, both Fedor and Sergey will play optimally. Fedor makes the first move. Who is going to win?

Input
The first line of the input file contains an integer n — the number of heaps (1 ≤ n ≤ 5). The second line of the input file contains n integers a1, a2,..., an — the amounts of problems in each heap.

Output
Output "FEDOR" (without quotes) if Fedor will win, or "SERGEY" (without quotes) otherwise.

Example(s)
sample input
sample output
3
5 5 5
FEDOR

sample input
sample output
4
3 1 2 3
SERGEY

<|response|>
1) Abridged problem statement
- You have n heaps in a line with sizes a1, a2, ..., an (n ≥ 1).
- Players alternate. On a move, a player chooses either the current first or current last heap and removes any positive number of stones from that heap. Empty heaps disappear.
- The player who cannot move (all heaps are gone) loses. Fedor moves first.
- Determine the winner assuming optimal play.

2) Key observations
- With 2 heaps this is just Nim on two piles: the player to move loses if and only if the two piles are equal.
- For more heaps, only the current ends are accessible. The middle segment acts like a "transform" between the ends.
- Define g[l, r](x): for the fixed middle a[l+1..r−1], it maps the left-end size x ≥ 1 to the unique right-end size y ≥ 1 that makes (x, middle, y) a losing (P) position; if no such y exists, define g[l, r](x) = 0 (a sentinel).
- For fixed x, at most one losing y exists (otherwise you could move between two losing positions).
- Each mapping g[l, r] can be encoded by a pair (L, R) with a simple rule:
  - If x is outside [min(L, R), max(L, R)], then g(x) = x (identity).
  - If x is inside, g moves one step toward R:
    - If L ≤ R: g(x) = x + 1 for x < R, and g(R) = 0.
    - If L > R: g(x) = x − 1 for x > R, and g(R) = 0.
- Base case (length 2): middle is empty, and losing happens only when the ends are equal. This is the identity mapping, i.e., the pair (0, 0).
- Inversion: the inverse mapping (desired right-end → losing left-end) is obtained by swapping the pair: inv(L, R) = (R, L).
- DP recurrence:
  - L = g[l+1, r](a[l+1])  (the losing right-end if we clear the leftmost heap first).
  - R = inv(g[l, r−1])(a[r−1])  (the losing left-end if we clear the rightmost heap first).
  - Store g[l, r] as the pair (L, R).
- Final decision:
  - Compute target = g[1, n](a1) via the pair for the whole interval.
  - If target equals an, the starting position is losing for Fedor → print SERGEY; otherwise print FEDOR.
  - Special case n = 1: Fedor takes the only heap and wins.

3) Full solution approach
- Represent each interval [l, r] by a pair (L, R) encoding g[l, r].
- Implementation of the mapping apply_func((L, R), x):
  - Let lo = min(L, R), hi = max(L, R).
  - If x < lo or x > hi, return x.
  - Otherwise:
    - If L ≤ R: return x + 1 if x < R else 0.
    - If L > R: return x − 1 if x > R else 0.
- DP:
  - Initialize g[l][r] = (0, 0) for all l, r (this already serves as the base for intervals of length 2).
  - For length = 3..n:
    - For each l, set r = l + length − 1.
    - L = apply_func(g[l+1][r], a[l+1]).
    - R = apply_func(inv(g[l][r−1]), a[r−1]) where inv swaps the pair.
    - Set g[l][r] = (L, R).
- Answer:
  - If n == 1, print FEDOR.
  - Else compute target = apply_func(g[0][n−1], a[0]).
  - Print SERGEY if target == a[n−1], else FEDOR.
- Complexity: O(n^2) time and memory; independent of the magnitude of ai.

4) C++ implementation

```cpp
#include <bits/stdc++.h>
using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
}

int n;
vector<int> a;

static inline int apply_func(pair<int, int> fn, int x) {
    // apply_func represents the middle transform g[l,r](x) with a pair (L, R)
    // and applies it to x as described in the analysis.

    int L = fn.first, R = fn.second;
    int lo = min(L, R), hi = max(L, R);
    // If x is outside [lo, hi], return x unchanged
    if(max(lo, min(x, hi)) != x) {
        return x;
    }
    // Otherwise step toward R by +1 if L <= R else -1;
    // hitting R maps to 0
    int step;
    if(L <= R) {
        step = 1;
    } else {
        step = -1;
    }
    if(x != R) {
        return x + step;
    } else {
        return 0;
    }
}

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // There is a direct O((n*max)^2) solution with DP, but this is too slow
    // under the given constraints. Instead, we will make a series of
    // observations and derive a O(n^2) solution.
    //
    // - With two heaps, this is Nim on 2 piles: the player to move loses
    //   exactly when the two ends are equal (a[1] == a[2]).
    //
    // - For more heaps, the middle segment acts like a transform that maps
    //   the leftmost size x to the unique rightmost size y that makes the
    //   position losing (a P-position). Call this mapping g[l,r](x).
    //
    // - To show the uniqueness of the losing y for a given x, consider the
    //   following:
    //     (1) Any q < g[l,r](x) can be reached in a single move; if such a q
    //         were losing, then g[l,r](x) would be winning - contradiction.
    //     (2) Any q > g[l,r](x) is winning because it can move to g[l,r](x),
    //         which is losing by definition.
    //
    // - By looking of the structure of g[l,r], and an argument similar to
    //   above, we can notice that we can encode each g[l,r] by a pair (L, R):
    //     (1) If x is outside the closed interval between L and R, g(x) = x.
    //         Intuitively, we can think of this as a symmetry argument, as the
    //         "inner" range is effectively losing.
    //     (2) If x lies inside that interval, g[l,r](x) moves by one toward R;
    //         for example if moving, g[l,r](R) = 0 (meaning: there is no
    //         positive y that makes the position losing).
    //
    // - We can build up g[l,r] recursively:
    //     (1) Let g[l,r] store the pair (L, R) that encodes it.
    //     (2) For intervals of length 2, the middle is empty, so g is identity,
    //         or g = (0, 0). Expanding here, the only losing states are when
    //         the second player mirrors the first (Nim on 2 heaps).
    //     (3) For length >= 3, we can reuse the already computed g[l+1,r] and
    //         g[l,r-1] to compute g[l,r]:
    //         * g[l+1,r](a[l+1]) gives us the unique losing value for a[r]
    //           assuming a[l] has been cleared. Denote it L'.
    //         * inv(g[l,r-1])(a[r-1]) gives us the unique loosing value for
    //           a[l] assuming a[r] has been cleared. Denote it R'.
    //         * WLOG, assume L' < R'. We can notice immediately that g[l,r](x)
    //           can't be L' because we can win by fully clearing a[l]. We can
    //           also notice that g[l,r](x) = x for x < L' because if a[l] =
    //           a[r] = x, the second player can mirror the first one until the
    //           game ends. This requires some time to get convinced. Let's now
    //           consider x = L'. We can show that a[r] = L'+1 is losing for
    //           the first player, because all reachable states (reduction in
    //           a[l] or a[r]) are winning. This is one of the key observations
    //           - by similar logic, we can show that g[l,r](L'+1) = L'+2, and
    //           so on, until we reach R' where we have to think a bit more.
    //           Intuitively, we should expect g[l,r](R') = R'+1 using the
    //           same "cascading" logic, but we will show that g[l,r](R') = 0,
    //           meaning there is no y that makes the position losing. This is
    //           because we know that a[l] = R' is losing if a[r] is cleared. We
    //           are now left with a[l] > R'. In this case, if a[r] = R', the
    //           second player can either immediately force the first one into
    //           one of the above-described losing states, or if the first
    //           player goes to a[l] = R', the second player can clear a[r] and
    //           win.
    //     (4) The case L' > R' is symmetric. We can notice that g[l,r] can be
    //         "inverted" for the L',R'. This is particularly useful because
    //         it gives us the function f(x) = y meaning the loosing a[l] = y
    //         when a[r] = x. We compute R' precisely this way.
    //
    // - Final decision is simple:
    //     Fedor (first player) wins unless a[n] == g[1,n](a[1]).

    if(n == 1) {
        cout << "FEDOR\n";
        return;
    }

    // g[l][r] encodes g[l,r] as a pair (L, R)
    vector<vector<pair<int, int>>> g(n, vector<pair<int, int>>(n, {0, 0}));

    for(int len = 3; len <= n; ++len) {
        for(int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            g[l][r] = {
                // L_{l,r} = g[l+1,r](a[l+1])
                apply_func(g[l + 1][r], a[l + 1]),
                // R_{l,r} = inv(g[l,r-1]) applied to a[r-1]
                apply_func({g[l][r - 1].second, g[l][r - 1].first}, a[r - 1])
            };
        }
    }

    int target = apply_func(g[0][n - 1], a[0]);
    if(target == a[n - 1]) {
        cout << "SERGEY\n";
    } else {
        cout << "FEDOR\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5) Python implementation

```python
import sys


def apply_func(fn, x):
    L, R = fn
    lo, hi = (L, R) if L <= R else (R, L)
    if x < lo or x > hi:
        return x
    step = 1 if L <= R else -1
    if x != R:
        return x + step
    else:
        return 0


def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    if n == 1:
        print("FEDOR")
        return

    g = [[(0, 0) for _ in range(n)] for __ in range(n)]

    for length in range(3, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1
            L = apply_func(g[l + 1][r], a[l + 1])
            inv_pair = (g[l][r - 1][1], g[l][r - 1][0])
            R = apply_func(inv_pair, a[r - 1])
            g[l][r] = (L, R)

    target = apply_func(g[0][n - 1], a[0])
    print("SERGEY" if target == a[n - 1] else "FEDOR")


if __name__ == "__main__":
    solve()
```
