CF341E Candies Game

Iahub is playing an uncommon game. Initially, he has $ n $ boxes, numbered 1, 2, 3, $ ... $ , $ n $ . Each box has some number of candies in it, described by a sequence $ a_{1} $ , $ a_{2} $ , $ ... $ , $ a_{n} $ . The number $ a_{k} $ represents the number of candies in box $ k $ . The goal of the game is to move all candies into exactly two boxes. The rest of $ n-2 $ boxes must contain zero candies. Iahub is allowed to do several (possible zero) moves. At each move he chooses two different boxes $ i $ and $ j $ , such that $ a_{i}

The first line of the input contains integer $ n $ ( $ 3

In case there exists no solution, output -1. Otherwise, in the first line output integer $ c $ $ (0

For the first sample, after the first move the boxes will contain 3, 12 and 3 candies. After the second move, the boxes will contain 6, 12 and 0 candies. Now all candies are in exactly 2 boxes. For the second sample, you can observe that the given configuration is not valid, as all candies are in a single box and they should be in two boxes. Also, any move won't change the configuration, so there exists no solution. For the third sample, all candies are already in 2 boxes. Hence, no move is needed.