Sequence Folding

Alice and Bob are practicing hard for the new ICPC season. They hold many private contests where only the two of them compete against each other. Their knowledge and skills are so close that many times they tie in both the number of problems solved and the time penalty! To break the tie, Alice and Bob invented a tie-breaker technique called sequence folding. The steps of this technique are as follows:

1. Generate a random integer N \geq 2.

2. Generate a sequence of $N$ random integers.

3. If N = 2, go to step 6.

4. Fold the sequence: add the $N$-th element to the first, the (N-1)-th to the second, and so on; if $N$ is odd, the middle element is added to itself. Figure 1 illustrates the process.

5. Set N = \lceil N/2 \rceil and go to step 3.

6. When only two numbers remain, if the first is greater than the second, Alice wins; otherwise, Bob wins.

Figure 1.a Before folding

Figure 1.b After one folding step

Figure 1.c After two folding steps, Alice wins!

In this problem, you are given a sequence of $N$ integers and are asked to determine the contest winner using the sequence folding tie-breaker technique.