Two-Player Stone Picking Game

A company is hosting a brain‐teasing two‐player stone picking game. There are N piles of stones arranged in a row; the i-th pile contains a_i stones. Before the game begins, the company deliberately removes some piles. Then the two players take turns; on each turn a player must remove one whole pile – but they can remove only those piles that satisfy the following rule:

• A pile can be removed if at least one of its neighbors has already been removed. (A pile’s neighbors are the piles immediately to its left and right. Note that the first pile is adjacent only to the second and the last only to the second‐last.)

The game ends when no available pile remains. The final score for each player is the sum of stones they collected, and the winner is the one with the higher total. Assuming that both players use optimal strategies, determine the final scores for the first mover and the second mover.

Game details:

• The piles are numbered from 1 to N.
• For each pile, if it is available then it initially has not yet been taken. However, some piles will already have been removed by the company before the game starts.
• When a player removes a pile, they collect all the stones in that pile. After removal, the adjacent piles (if still available) become "activated" – meaning that if a pile is not adjacent to any removed pile it cannot be taken.
• In a contiguous block (or segment) of available piles, only those at the ends may be removed initially unless the segment is activated from one side by a previously removed pile. In fact, if one end is activated, the removal in that segment will be forced from that end until possibly both ends become activated. When both ends are activated the segment behaves like a standard two‐end coin game.

More formally, if a contiguous segment of available piles has indices from l to r, then:

• The left end is activated if l > 1 and pile l-1 was removed by the company, and similarly the right end is activated if r < N and pile r+1 was removed.
• If neither end is activated, the segment is locked and no move can ever be made in that segment.
• If exactly one end is activated, the moves in that segment are forced from that end; the stones collected by the mover in that segment are exactly the alternating sum (taking the pile at the activated end, then the next, and so on).
• If both ends are activated then the segment is equivalent to the classical two‐end coin game where players choose either the leftmost or rightmost pile. The optimal difference can be computed using the recurrence \[ f(l,r)=\max\{a_l - f(l+1,r),\; a_r - f(l,r-1)\},\] with the base case \(f(l,l)=a_l\). If the total sum of stones in the segment is \(S\) and the computed difference is \(d\), then the mover’s score from that segment is \((S+d)/2\) and the other player’s score is \((S-d)/2\).

The entire game is the disjunctive sum of such segments. Note that when players may choose in which segment to make a move, the overall outcome is determined by sorting the segments by their advantage value (\(d\)). If a segment is played by the player whose turn it is, they obtain an advantage of \(d\) for that segment; if the opponent gets to start that segment later, the advantage is \(-d\). Under optimal play, the first player will choose the segments with the largest advantage. Let the advantages (\(d\)) of the playable segments be sorted in descending order as \(d_1, d_2, \dots, d_k\) and let \(S_{total}\) be the sum of stones in these segments. Then the overall outcome (difference) is

[ overall_diff = \sum_{i ;\text{even}} d_{i+1} - \sum_{i ;\text{odd}} d_{i+1},]

and the final scores are

[ \text{first player} = \frac{S_{total}+overall_diff}{2}, \qquad \text{second player} = \frac{S_{total}-overall_diff}{2}.]

inputFormat

The input consists of three lines:

1. An integer N representing the number of piles.
2. N space‐separated integers, where the i-th integer is ai, the number of stones in pile i.
3. A string of length N made up of characters '0' and '1'. A character '1' means that the corresponding pile has been removed by the company before the game begins, and '0' means the pile is available.

You may assume that the game is played on 1-indexed piles.

outputFormat

Output two space‐separated integers: the final total stone counts collected by the first player and the second player respectively, assuming optimal play by both.

sample

5
1 2 3 4 5
10001

6 3