CF178A2 Educational Game

The Smart Beaver from ABBYY began to develop a new educational game for children. The rules of the game are fairly simple and are described below. The playing field is a sequence of $ n $ non-negative integers $ a_{i} $ numbered from $ 1 $ to $ n $ . The goal of the game is to make numbers $ a_{1},a_{2},...,a_{k} $ (i.e. some prefix of the sequence) equal to zero for some fixed $ k $ $ (k

The first input line contains a single integer $ n $ . The second line contains $ n $ integers $ a_{i} $ ( $ 0

Print exactly $ n-1 $ lines: the $ k $ -th output line must contain the minimum number of moves needed to make the first $ k $ elements of the original sequence $ a_{i} $ equal to zero. Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64d specifier.