Regarding How a Simple DFS Problem I Thought Was Problem A Became Problem E in This Contest (Easy)

Time limit2sMemory limit512 MB

Summary
Given a perfect binary tree with N = 2^k - 1 weighted nodes numbered in heap order and an implied axis-aligned layout, find the maximum sum of weights inside any axis-parallel rectangle whose sides don't cross a node.
Level

Hard9 of 10

Topics
Divide and conquer, Dynamic programming, Tree, Recursion
Solved
No attempts yet

Problem

Ukje drew a 🎄perfect binary tree🎄 on paper. He also filled the nodes with integer weights. Ukje wants to choose a suitable rectangular region and maximize the sum of the weights of the nodes inside the region. The rectangle must contain at least one node, and it must not be tilted.

The definitions omitted from the problem are as follows. Read them if anything is unclear.

  1. The rectangle is parallel to the axes, and its sides must not cross a node.
  2. For every node u, the x-coordinate of every node in the left subtree of u is less than the x-coordinate of u.
  3. For every node u, the x-coordinate of every node in the right subtree of u is greater than the x-coordinate of u.
  4. The y-coordinate of a child node is less than the y-coordinate of its parent node.
  5. All nodes at the same depth in the tree have the same y-coordinate.

Input

The first line gives the number of nodes N. (1 ≤ N ≤ 262,143, and N is a natural number of the form 2k-1)

The second line gives the node weights Wi in node number order. (-109 ≤ Wi ≤ 109)

The root node is numbered 1, and the left and right children of node i are numbered 2Ă—i and 2Ă—i+1, respectively.

Output

Print the maximum sum of weights that Ukje can obtain.

Examples2

  1. Example 1

    Input
    15
-2 8 -3 -9 0 -6 3 4 -1 10 -1 7 -100 7 -1
    Expected output
    24

  2. Example 2

    Input
    7
10 -15 -1 4 3 -7 9
    Expected output
    14