完全二叉树的权值（润色版）

题目描述

给你一棵有 N 个节点的完全二叉树。节点按层序（从上到下、从左到右）编号为 A1, A2, ..., AN，如下图所示。

根的深度为 1；根的左、右孩子深度为 2；以此类推。

把同一深度上的所有节点权值相加，问：哪一层（深度）的权值和最大？ 如果有多层并列最大，输出编号最小的那一层。

输入格式

• 第一行：整数 N —— 节点个数。
• 第二行：N 个整数 A1 A2 ... AN —— 按层序给出的每个节点的权值。

输出格式

• 输出一个整数：权值和最大的深度。若有并列，输出最小的深度。

样例

输入

7
1 6 5 4 3 2 1

输出

2

解释

• 深度 1：A1 = 1，和为 1
• 深度 2：A2 + A3 = 6 + 5 = 11
• 深度 3：A4 + A5 + A6 + A7 = 4 + 3 + 2 + 1 = 10 最大的是深度 2。

数据范围

• 1 ≤ N ≤ 1e5
• |Ai| ≤ 1e5（可为负数或零）