CF245C Game with Coins

Two pirates Polycarpus and Vasily play a very interesting game. They have $ n $ chests with coins, the chests are numbered with integers from 1 to $ n $ . Chest number $ i $ has $ a_{i} $ coins. Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer $ x $ $ (2·x+1

The first line contains a single integer $ n $ $ (1

Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.

In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests. In the second sample there is only one possible move $ x=1 $ . This move should be repeated at least 3 times to empty the third chest.