Splitting Bottles Game

Tony and Ray recently became addicted to a game called Splitting. The rules are as follows:

There are \(n\) bottles numbered \(0,1,\ldots,n-1\). The \(i\)th bottle contains \(p_i\) chocolate beans initially. Two players take turns making moves with Tony moving first. In each move a player must choose three bottles with indices \(i, j, k\) satisfying \[ i < j,\quad j \le k,\quad 0 \le i,j,k \le n-1. \] The move is only allowed if bottle \(i\) contains at least one bean. The player then takes one bean from bottle \(i\) and adds one bean to bottle \(j\) and one bean to bottle \(k\) (note that it is allowed that \(j=k\), in which case two beans are added to bottle \(j\)).

The game ends when the current player cannot make a move according to the rules (i.e. there is no bottle \(i < n-1\) with at least one bean available). The player who is unable to move loses, and the winner gets all the chocolate beans.

Tony wants to ensure that he can eventually obtain all the chocolate beans by winning the game. In order to do so he must have a winning strategy. Given the initial bean counts in each bottle, determine whether Tony has a forced win if he moves first. If he can force a win then you must also output one valid winning first move (i.e. a triple of indices \(i, j, k\) as specified) and compute how many different winning first moves there are.

Note: Moves affect the state as follows: if a move is made using bottle \(i\) (with at least one bean), then its bean count decreases by one, and the bean counts of bottles \(j\) and \(k\) each increase by one (if \(j=k\) then the chosen bottle gets two extra beans). However, only bottles with indices less than \(n-1\) can be used as the source of a move; that is, bottle \(n-1\) is terminal.

Game theory background (optional): This is an impartial game. Define a Grundy value \(G(v)\) for a bottle at position \(v\) where \(0 \le v \le n-1\) as follows. A move starting from bottle \(v\) removes one bean from it and places beans into bottles with indices greater than \(v\). In particular, for \(v=n-1\) we have \(G(n-1)=0\) (terminal position) and for \(v \le n-2\) we define \[ G(v)=\operatorname{mex}\{G(j) \oplus G(k): j,k \text{ satisfy } v<j\le k\le n-1\}. \] In the disjunctive sum the overall nim‐value is the xor of the grundy values of all positions (counted with parity). Tony can force a win if and only if the overall nim sum \[ S=\bigoplus_{i=0}^{n-2}\Bigl(\underbrace{G(i) \oplus G(i) \oplus \cdots \oplus G(i)}_{p_i \text{ mod }2 \text{ times}}\Bigr) \] is nonzero. Moreover, a winning move is one that changes the nim sum to \(0\). In a move the effect on the nim sum is to remove \(G(i)\) and add \(G(j)\) and \(G(k)\) (if \(j=k\) then technically \(G(j)\) is added twice, canceling out).

inputFormat

The first line contains a single integer \(n\) (\(3 \le n \le 50\)), the number of bottles. The second line contains \(n\) space‐separated integers \(p_0, p_1, \ldots, p_{n-1}\) (\(0 \le p_i \le 10^9\)), where \(p_i\) is the number of chocolate beans in bottle \(i\) initially.

Note that only bottles with index less than \(n-1\) can be chosen as the source in a move.

outputFormat

If Tony has a winning strategy, print three lines:

• First line: YES
• Second line: three integers \(i\), \(j\), \(k\) representing one valid winning first move (choose the lexicographically smallest if there are many).
• Third line: the total number of winning first moves.

If Tony does not have a winning strategy, print a single line containing NO.

sample

3
1 0 0

NO