#include <cassert>
#include <iostream>

// Discovering the growth of a recurrence
//
// We have already considered:
//
//     T(n) = T(n/2) + 1,
//
// where we solve ONE problem of approximately half
// the original size.
//
// This gave:
//
//     T(n) = Theta(log(n)).
//
// Now consider:
//
//             /
//            (   1                    n = 1
//             )
//     T(n) = <
//             )
//            (   2*T(n/2) + n        n > 1.
//             \
//
// There are two important differences:
//
//     1. We now solve TWO problems of approximately
//        half the original size.
//
//     2. We perform an additional n units of work.
//
// Author the function T(n), asserting that:
//
//     n >= 1.
//
// Then, in main(), write a loop that calculates:
//
//     T(1), T(2), T(3), ...
//
// Try to determine how quickly T(n) grows.
//
// If the values of T(n) do not immediately suggest
// a pattern, also examine:
//
//     T(n)/n.
//
// Pay particular attention to powers of two.

// Function declarations
int main();

unsigned long long T(
    unsigned int const n
);

// Function definitions
int main() {
    // Your implementation here.

    return 0;
}


// unsigned long long T( ... )
//
// @param n
//     A positive integer.
//
// @returns
//     The value defined recursively by:
//
//         T(1) = 1
//
//     and:
//
//         T(n) = 2*T(n/2) + n
//
//     for n > 1.

unsigned long long T(
    unsigned int const n
) {
    assert( n >= 1 );

    // Your implementation here.

    return 1;
}














































// Hint
//
// Begin by printing:
//
//     T(1)
//     T(2)
//     T(3)
//     ...
//
// For example:
//
//     for ( unsigned int k{ 1 };
//           k <= 20;
//           ++k ) {
//         std::cout << "T(" << k << ") = "
//                   << T( k )
//                   << std::endl;
//     }
//
// If the pattern is not obvious, try printing:
//
//     T(n)/n.
//
// In particular, pay attention to:
//
//     n = 1
//     n = 2
//     n = 4
//     n = 8
//     n = 16
//
// What do these values have in common?














































// Solution

/*
int main() {
    for ( unsigned int k{ 1 };
          k <= 20;
          ++k ) {
        std::cout << "T(" << k << ") = "
                  << T( k )
                  << std::endl;
    }

    std::cout << std::endl;

    for ( unsigned int k{ 1 };
          k <= 20;
          ++k ) {
        std::cout << "T(" << k << ")/" << k
                  << " = "
                  << T( k )/(1.0*k)
                  << std::endl;
    }

    return 0;
}

unsigned long long T(
    unsigned int const n
) {
    assert( n >= 1 );

    if ( n == 1 ) {
        return 1;
    } else {
        return 2*T( n/2 ) + n;
    }
}
*/














































// What is the pattern?
//
// The first values of T(n) are:
//
//     T(1)  =   1
//     T(2)  =   4
//     T(3)  =   5
//     T(4)  =  12
//     T(5)  =  13
//     T(6)  =  16
//     T(7)  =  17
//     T(8)  =  32
//     T(9)  =  33
//     T(10) =  36
//     T(11) =  37
//     T(12) =  44
//     T(13) =  45
//     T(14) =  48
//     T(15) =  49
//     T(16) =  80
//     T(17) =  81
//     T(18) =  84
//     T(19) =  85
//     T(20) =  92
//
//
// The pattern is not particularly obvious.
//
// Let us instead examine T(n)/n:
//
//     T(1)/1   = 1             <----
//
//     T(2)/2   = 2             <----
//
//     T(3)/3   = 1.66667
//
//     T(4)/4   = 3             <----
//
//     T(5)/5   = 2.6
//     T(6)/6   = 2.66667
//     T(7)/7   = 2.42857
//
//     T(8)/8   = 4             <----
//
//     T(9)/9   = 3.66667
//     T(10)/10 = 3.6
//     T(11)/11 = 3.36364
//     T(12)/12 = 3.66667
//     T(13)/13 = 3.46154
//     T(14)/14 = 3.42857
//     T(15)/15 = 3.26667
//
//     T(16)/16 = 5             <----
//
//
//
// Powers of two
//
// Once again, powers of two reveal the pattern:
//
//     T(1)/1   = 1
//
//     T(2)/2   = 2
//
//     T(4)/4   = 3
//
//     T(8)/8   = 4
//
//     T(16)/16 = 5.
//
// Therefore, we might predict:
//
//     T(32)/32 = 6
//
// and:
//
//     T(64)/64 = 7.
//
// Recall:
//
//     log_2(1)  = 0
//     log_2(2)  = 1
//     log_2(4)  = 2
//     log_2(8)  = 3
//     log_2(16) = 4.
//
// Thus, when n is a power of two:
//
//     T(n)/n = log_2(n) + 1.
//
// Multiplying both sides by n gives:
//
//     T(n) = n*log_2(n) + n.
//
//
//
// IMPORTANT:
//
// This is an exact formula when n is a power of two.
//
// It is NOT the exact formula for every positive
// integer n for the recurrence as we have written
// it.
//
// Why?
//
// Because C++ integer division is used.
//
// For example:
//
//     T(3)
//
//       = 2*T(3/2) + 3
//
//       = 2*T(1) + 3
//
//       = 5.
//
// But:
//
//     3*log_2(3) + 3
//
// is approximately:
//
//     7.75.
//
// Thus:
//
//     T(n) = n*log_2(n) + n
//
// should not be claimed as the exact solution for
// arbitrary n.
//
//
//
// Deriving the formula for powers of two
//
// Suppose:
//
//     n = 2^k.
//
// Then:
//
//     T(n) = 2*T(n/2) + n.
//
// Substitute again:
//
//     T(n)
//
//       = 2*(2*T(n/4) + n/2) + n
//
//       = 4*T(n/4) + n + n
//
//       = 4*T(n/4) + 2*n.
//
// Substitute again:
//
//     T(n)
//
//       = 8*T(n/8) + 3*n.
//
// After j substitutions:
//
//     T(n)
//
//       = 2^j*T(n/2^j) + j*n.
//
//
//
// When does this stop?
//
// We stop when:
//
//     n/2^j = 1.
//
// Therefore:
//
//     2^j = n,
//
// and hence:
//
//     j = log_2(n).
//
// Thus:
//
//     T(n)
//
//       = n*T(1) + n*log_2(n).
//
// Since:
//
//     T(1) = 1,
//
// we obtain:
//
//     T(n)
//
//       = n + n*log_2(n).
//
// Therefore, for powers of two:
//
//     T(n) = n*log_2(n) + n.
//
//
//
// What about asymptotic growth?
//
// We have:
//
//     n*log_2(n) + n.
//
// For large n, the:
//
//     n*log_2(n)
//
// term dominates the:
//
//     n
//
// term.
//
// Therefore:
//
//     T(n) = Theta(n*log(n)).
//
// This is the important conclusion.
//
// Even when n is not a power of two, the recurrence
// still has:
//
//     Theta(n*log(n))
//
// growth.
//
//
//
// A recursion tree
//
// There is another very useful way to understand
// this recurrence.
//
// Suppose:
//
//     n = 8.
//
// At the top level:
//
//                         8
//
// we perform 8 units of additional work.
//
// We then create TWO problems of size 4:
//
//                    4         4
//
// Each performs 4 units of additional work.
//
// Therefore, the total work at this level is:
//
//     4 + 4 = 8.
//
// Each problem of size 4 creates two problems of
// size 2:
//
//                2   2       2   2
//
// The total work at this level is:
//
//     2 + 2 + 2 + 2 = 8.
//
// Finally:
//
//             1 1 1 1     1 1 1 1
//
// Again, the total is:
//
//     8.
//
//
//
// We can picture the work as:
//
//                    n                     n
//
//              /           \
//
//            n/2           n/2             n
//
//           /   \         /   \
//
//         n/4   n/4     n/4   n/4          n
//
//         ...   ...     ...   ...
//
//
// At EVERY level, the total amount of work is
// approximately:
//
//     n.
//
//
//
// How many levels are there?
//
// Each level halves the size of each problem:
//
//     n
//
//     n/2
//
//     n/4
//
//     n/8
//
//     ...
//
//     1.
//
// We have already seen that repeated halving gives:
//
//     log_2(n)
//
// levels.
//
// Thus:
//
//     work per level
//
//         approximately n
//
// multiplied by:
//
//     number of levels
//
//         approximately log_2(n)
//
// gives:
//
//     approximately n*log_2(n).
//
// This is another way to understand why:
//
//     T(n) = Theta(n*log(n)).
//
//
//
// Compare with the previous recurrence
//
// Previously:
//
//     T(n) = T(n/2) + 1.
//
// There was ONE recursive problem:
//
//                  n
//                  |
//                  v
//                 n/2
//                  |
//                  v
//                 n/4
//                  |
//                  v
//                 ...
//
//
// This gave:
//
//     Theta(log(n)).
//
//
//
// Now:
//
//     T(n) = 2*T(n/2) + n.
//
// There are TWO recursive problems:
//
//                       n
//
//                    /     \
//
//                  n/2     n/2
//
//                 /  \     /  \
//
//               n/4 n/4  n/4 n/4
//
//                  ...
//
//
// The number of recursive problems grows as we move
// downward through the recursion tree.
//
// At the same time, each individual problem becomes
// smaller.
//
// The interesting result is that the total amount of
// work at each level remains approximately n.
//
//
//
// Where does this occur?
//
// A very important example is merge sort.
//
// We will study the details of merge sort later.
//
// For now, suppose we want to sort an array
// containing n entries.
//
// Merge sort follows this general strategy:
//
//     1. Sort the first half.
//
//     2. Sort the second half.
//
//     3. Merge the two sorted halves.
//
//
//
// Schematically:
//
//     [              unsorted              ]
//
//                        |
//              -------------------
//              |                 |
//
//              v                 v
//
//     [ first half ]     [ second half ]
//
//              |                 |
//              v                 v
//
//     [   sorted   ]     [    sorted   ]
//
//              \                 /
//               \               /
//                ------   ------
//                      |
//                      v
//
//     [               sorted               ]
//
//
// Sorting the first half requires approximately:
//
//     T(n/2).
//
// Sorting the second half also requires:
//
//     T(n/2).
//
// Merging the two sorted halves requires work
// proportional to:
//
//     n.
//
// Therefore, a simplified recurrence describing
// merge sort is:
//
//     T(n) = 2*T(n/2) + n.
//
// This gives:
//
//     T(n) = Theta(n*log(n)).
//
//
//
// Counting merge-sort comparisons precisely
//
// There is an important distinction between:
//
//     a recurrence that models the growth
//
// and:
//
//     an exact count of comparisons.
//
// When merging two sorted arrays containing a total
// of n entries, we require at most:
//
//     n - 1
//
// comparisons.
//
// Also, when n is odd, the two halves need not
// contain exactly n/2 entries.
//
// Thus, the exact recurrence for merge sort requires
// a little more care.
//
// For understanding its asymptotic runtime, however:
//
//     T(n) = 2*T(n/2) + n
//
// is an excellent model.
//
// It captures the essential structure:
//
//     TWO problems of HALF the size
//
//                plus
//
//     LINEAR work to combine their solutions.
//
//
//
// Why is this better than selection sort?
//
// Recall that selection sort requires:
//
//     Theta(n^2)
//
// comparisons.
//
// Merge sort requires:
//
//     Theta(n*log(n)).
//
// Compare these growth rates:
//
//     n           n^2          n*log_2(n)
//
//     10          100              33
//
//     100       10000             664
//
//     1000    1000000            9966
//
//     10000 100000000          132877
//
//
// As n becomes larger, the difference becomes
// dramatic.
//
//
//
// For one million entries:
//
//     n = 1000000.
//
// Selection sort requires work proportional to:
//
//     n^2
//
//       = 1000000000000.
//
// That is approximately:
//
//     one trillion.
//
//
//
// Merge sort requires work proportional to:
//
//     n*log_2(n).
//
// Since:
//
//     log_2(1000000)
//
// is approximately:
//
//     19.93,
//
// we have approximately:
//
//     19930000.
//
// That is approximately:
//
//     twenty million.
//
//
//
// We should be careful:
//
// These expressions do NOT by themselves give the
// exact running time in seconds.
//
// They describe how the amount of work grows.
//
// Nevertheless, comparing:
//
//     approximately 10^12
//
// with:
//
//     approximately 2*10^7
//
// explains why the difference between:
//
//     Theta(n^2)
//
// and:
//
//     Theta(n*log(n))
//
// matters enormously for large inputs.
//
//
//
// A useful way to remember this recurrence
//
// Consider:
//
//     T(n) = 2*T(n/2) + n.
//
// The:
//
//     2
//
// tells us that each problem creates TWO recursive
// problems.
//
// The:
//
//     n/2
//
// tells us that each recursive problem is HALF the
// size.
//
// The final:
//
//     + n
//
// tells us that we perform LINEAR additional work
// at each problem.
//
//
//
// These three pieces determine the structure:
//
//                  T(n)
//
//              /           \
//
//          T(n/2)         T(n/2)
//
//              \           /
//
//            additional work:
//
//                    n
//
//
// This is our first significant example of a
// divide-and-conquer recurrence.
//
//
//
// Divide and conquer
//
// The general idea is:
//
//     DIVIDE
//
//         Break a problem into smaller problems.
//
//
//     CONQUER
//
//         Solve those smaller problems.
//
//
//     COMBINE
//
//         Use their solutions to solve the original
//         problem.
//
//
// For merge sort:
//
//     DIVIDE
//
//         Divide the array into two halves.
//
//
//     CONQUER
//
//         Sort each half.
//
//
//     COMBINE
//
//         Merge the two sorted halves.
//
//
//
// Questions:
//
// 1. What values do you obtain for T(1) through
//    T(20)?
//
// 2. Why is the pattern easier to see by examining
//    T(n)/n?
//
// 3. What happens to T(n)/n when n is a power of
//    two?
//
// 4. For powers of two, what is the exact formula
//    for T(n)?
//
// 5. Why is:
//
//        n*log_2(n) + n
//
//    NOT the exact formula for every positive
//    integer n in this implementation?
//
// 6. Why is the runtime nevertheless:
//
//        Theta(n*log(n))?
//
// 7. In the recursion tree, why is the total work
//    at each level approximately n?
//
// 8. How many levels are there in the recursion
//    tree?
//
// 9. How does:
//
//        n work per level
//
//    multiplied by:
//
//        log_2(n) levels
//
//    lead to:
//
//        Theta(n*log(n))?
//
// 10. What do the two recursive calls represent in
//     merge sort?
//
// 11. What does the additional n work represent?
//
// 12. Why does merge sort scale much better than
//     selection sort for large arrays?
//
//
//
// Our recurrence progression now includes:
//
//     T(n) = T(n - 1) + 1
//
//              Theta(n)
//
//
//
//     T(n) = T(n - 1) + n
//
//              Theta(n^2)
//
//
//
//     T(n) = n*T(n - 1) + n
//
//              Theta(n!)
//
//
//
//     T(n) = T(n/2) + 1
//
//              Theta(log(n))
//
//
//
//     T(n) = 2*T(n/2) + n
//
//              Theta(n*log(n))
//
//
// These examples demonstrate that the structure of
// the recursive calls matters enormously.
//
// Ask:
//
//     How many recursive problems are created?
//
//     How large is each recursive problem?
//
//     How much additional work is performed?
//
//
// Those three questions will help us understand the
// runtime of many recursive algorithms.
//
// In particular, they will explain why divide-and-
// conquer algorithms such as merge sort can be so
// much more efficient than the simpler sorting
// algorithms we have studied so far.