B. Om Nom and Dark Park

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Om Nom is the main character of a game "Cut the Rope". He is a bright little monster who likes visiting friends living at the other side of the park. However the dark old parks can scare even somebody as fearless as Om Nom, so he asks you to help him.

The park consists of 2n + 1 - 1 squares connected by roads so that the scheme of the park is a full binary tree of depth n. More formally, the entrance to the park is located at the square 1. The exits out of the park are located at squares 2n, 2n + 1, ..., 2n + 1 - 1 and these exits lead straight to the Om Nom friends' houses. From each square i (2 ≤ i < 2n + 1) there is a road to the square . Thus, it is possible to go from the park entrance to each of the exits by walking along exactly n roads.

To light the path roads in the evening, the park keeper installed street lights along each road. The road that leads from square i to square  has ai lights.

Om Nom loves counting lights on the way to his friend. Om Nom is afraid of spiders who live in the park, so he doesn't like to walk along roads that are not enough lit. What he wants is that the way to any of his friends should have in total the same number of lights. That will make him feel safe.

He asked you to help him install additional lights. Determine what minimum number of lights it is needed to additionally place on the park roads so that a path from the entrance to any exit of the park contains the same number of street lights. You may add an arbitrary number of street lights to each of the roads.

Input

The first line contains integer n (1 ≤ n ≤ 10) — the number of roads on the path from the entrance to any exit.

The next line contains 2n + 1 - 2 numbers a2, a3, ... a2n + 1 - 1 — the initial numbers of street lights on each road of the park. Here ai is the number of street lights on the road between squares i and . All numbers ai are positive integers, not exceeding 100.

Output

Print the minimum number of street lights that we should add to the roads of the park to make Om Nom feel safe.

Sample test(s)

input

2
1 2 3 4 5 6

output

5

Note

Picture for the sample test. Green color denotes the additional street lights.

####################################editorial#################################

note:: arr[i] holds the number of street light betn i and floor(i/2)

First  of all we need to find the path which has the maximum number of street lights. This can be done by simply dividing all the leaf node by 2 till we reach the root node.

Now we need to place the max lights on each node. This is bit tricky. 

Suppose we are at node i, then we traverse all possible paths from here and see the maximum street light present , and we travel upwards from i to see the required number of lights to be added. We put the required number of lights on that edge that connects it to the heavy side(in terms of street light) and the go and repeat the same for levels below it. In case if street lights cannot be added at that level we further go down and add it to a position where it doesnot violate the condition of maximum count.  

   #########################code########################################

#include<iostream>

#include<stdio.h>

using namespace std;

long long int ret=0;

long long int  arr[200000];

long long int up=0;

long long int all(long long int start,long long int sum)

 {

  if(start>up)

  {

  if(sum>ret)ret=sum;

  }#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long c,hr,hb,wr,wb,f,s,ht,wt,wl,max=0;

    cin>>c>>hr>>hb>>wr>>wb;

        f=c/wr;

        wt=f*wr;

        ht=f*hr;

        wl=c-wt;

        s=wl/wb;

     //   wt+=s*wb;

        ht+=s*hb;

        max=ht;

        f--;

        while(f>=0)

        {

            wt=f*wr;

            ht=f*hr;

            wl=c-wt;

            s=wl/wb;

          //  wt+=s*wb;

            ht+=s*hb;

            if(ht>max)

                max=ht;

            f--;

        }

    cout<<max<<endl;

    return 0;

}

Chat Conversation End

  else

  {

  all(2*start,sum+arr[start]);

  all(2*start+1,sum+arr[start]);

  }

 }

int main()

{

long long int n;

cin>>n;

long long int x=1;

for(long long int t=1;t<=n;t++)

{

x=x*2;

}

up=2*x-1;

for(long long int i=2;i<=2+up-2;i++)

{

cin>>arr[i];

}

long long int mix=-1;

long long int sum=0;

long long int num;

for(long long int i=up;i>=x;i--)

{

sum=0;

num=i;

while(num!=1)

{

sum+=arr[num];

num=num/2;

}

if(sum>mix)

mix=sum;

}

// cout<<mix<<endl;

long long  int ans=0;

 for(long long int i=2;i<=up;i++)

  {

  // cout<<i<<endl;

 

        ret=0;

        long long int back_sum=0;

       for(long long int j=i;j>1;)

        {

        back_sum+=arr[j];

        j/=2;

        }

       //  cout<<"i "<<i<<" back_sum "<<back_sum<<endl;

        

        long long int ma=max(all(2*i,0),all(2*i+1,0));

       long long  int lit=mix-back_sum-ret;

        arr[i]+=lit;

        ans+=lit;

     

     

  }

   cout<<ans<<endl;

   return 0;

}