//
// Recursive sum of an array of integers, using "divide and conquor"
// a similar approach to binary search in a sorted array.
// -  We add the first half of the array to the second half of the array
//    - we add the first half of the array by halving it and adding its first half to its second half
//      - when we get only two elements, add them and if only one return it
//
// QUESTION: what is the complexity with respect to number of additions performed?
//

import java.util.*;

public class SumRec {

    public static int sum(int[] data,int lo,int hi){
	//System.out.println("sum: "+ lo +" "+ hi);
	//if (hi == lo) System.out.println("data["+ lo +"]");
	//if (hi - lo == 1) System.out.println("data["+ lo +"] + data["+ hi +"]");
	if (lo == hi) return data[lo];
	else if (hi - lo == 1) return data[lo] + data[hi];
	else return sum(data,lo,(lo+hi)/2) + sum(data,1+(lo+hi)/2,hi);
    }

     public static void main(String[] args) {
	 int n = Integer.parseInt(args[0]);
	 int[] data = new int[n];
	 Random gen = new Random();
	 for (int i=0;i<n;i++) data[i] = gen.nextInt(10); // in range 0 to 9
	 for (int x : data) System.out.print(x +" ");
	 System.out.println(" sums to "+ sum(data,0,n-1));
	 // is it right?
	 // int total = 0;
	 //for (int x: data) total = total + x;
	 //System.out.println(total);
     }
}