时间限制： 1.0 秒

空间限制： 512 MB

题目描述

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中，任何节点的两个子树高度相差不超过 1。若存在某一时刻某节点两个子树高度相差大于 1，则将通过对树旋转进行重新平衡以恢复此属性。图 1 至图 4 说明了旋转规则。

现给定关键码插入序列，序列中的关键码两两不同。在将他们按照先后顺序插入一个初始为空的 AVL 树中之后，请你求出 AVL 树根的关键码为多少。

输入格式

从标准输入读入数据。

第一行包含一个整数 $n$，为插入序列长度。

第二行包含 $n$ 个不同的整数，表示每个插入值。

输出格式

输出到标准输出。

输出一行一个整数，为最终形态 AVL 树根的关键码。

5
88 70 61 96 120

70

7
88 70 61 96 120 90 65

88

子任务

本题数据范围有所加强，对于所有数据，插入序列长度 $n\le 5\times 10^5$，所有关键码保证 $-10^9\le a_i\le 10^9$。

本题无数据梯度，需要通过全部数据获得所有分数。

来源

PAT 甲级 1066