#include <cstddef>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <vector>
#include <utility>
long long reduce(std::vector<long long> values) {
    if(values.empty()) return 0;
    while(values.size()>1) {
        std::vector<long long> next;next.reserve(values.size()/2+values.size()%2);
        for(std::size_t i=0;i<values.size();i+=2)
            next.push_back(values[i]+(i+1<values.size()?values[i+1]:0));
        values=std::move(next);
    }
    return values[0];
}
int main() {
    for(std::size_t n=0;n<100;++n) {
        std::vector<long long> v(n);for(std::size_t i=0;i<n;++i) v[i]=static_cast<long long>(i%11)-5;
        if(reduce(v)!=std::accumulate(v.begin(),v.end(),0LL)) throw std::runtime_error("oracle");
    }
    const std::vector<long long> input{3,1,4,1,5};std::vector<long long> scan(input.size());
    std::partial_sum(input.begin(),input.end(),scan.begin());
    if(reduce(input)!=14 || scan!=std::vector<long long>{3,4,8,9,14}) throw std::runtime_error("scan");
    std::cout<<"sum="<<reduce(input)<<" scan=";
    for(std::size_t i=0;i<scan.size();++i) std::cout<<(i?",":"")<<scan[i];std::cout<<'\n';
}