UCV2013J - Valences


Mr. White has found a way to maximize the purity of crystals based on certain chemical compounds. He has observed that each compound is made of molecules that are linked together following the structure of a complete binary tree where every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Each node of the tree stores the valence of a molecule and is represented as an integer number. Mr. White uses an electronic microscope that dumps the molecule structure as a stream of integer numbers and would like to have your help on automatically obtaining the total valence of only the leaves of the given tree. For example, the sequence 4-3-2-6-0-3 represents the tree shown in the figure and the total valence of the leaves is 9.

 

Sample Tree

Input

The input contains several test cases, each one corresponding to a particular compound. Each test case consists of a single line starting with an integer N (1 <= N <= 1000000), followed by N integer numbers Vi representing the valences of each molecule separated by blank spaces (0 <= Vi <= 100).

The end of input is indicated by a test case with N = 0.

Output

For each compound output a single line with the sum of the valences of the leaves of the tree.

Example

Input:
6 4 3 2 6 0 3
7 1 1 1 2 1 2 1
0 Output: 9
6

hide comments
$!:D: 2013-08-01 19:11:36

got AC...ws wrongly interpreting the ques

Last edit: 2013-08-02 10:12:03
Ouditchya Sinha: 2013-08-01 16:37:38

@$!:D : You are getting TLE on ideone. Try to think of a simpler way by working for small test cases N = 1,2,...,15. Try to observe the pattern. :)

ANKUR_MAHIWAL: 2013-08-01 08:54:52

finally accepted after a bit mistake

.: 2013-07-30 03:04:16

why wrong answer even when i have considered all the cases id 9747184,pls help
@Hector Navarro

Himanshu: 2013-07-29 19:41:37

piece of cake.....

chk: 2013-07-29 13:51:21

AC at first go! :)

aqfaridi: 2013-08-04 04:51:46

finally done 0.00 time..

Hector Navarro: 2013-07-28 00:38:43

@mostafa: when N=2 one node is the root and the other one is a leaf. They couldn't be both leaves

BISMITH BLAC: 2013-07-27 18:02:35

some more test cases...anyone...

Mostafa 36a2: 2013-07-27 12:25:18

first AC in AWK :)
I have a question : if N=2 why we consider only one node as a leaf , why not the two nodes?
another idea ... the molecule valences determine how many edges i think example:
a tree of 5 5 can't be expand more because no free edges (based on the Valences)


Added by:Hector Navarro
Date:2013-07-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Walter Hernández