Background

Special for beginners, ^_^

Description

根据给定的输入序列建立一棵平衡二叉树(AVL)，求出建立的平衡二叉树的树根。

Format

Input

输入一组测试数据。

数据的第 1 行给出一个正整数 N(n <= 20)，N 表示输入序列的元素个数；

第 2 行给出 N 个正整数 (整数 $\in[1, 10^9]$)，按数据给定顺序建立平衡二叉树。

Output

输出平衡二叉树的树根。

Samples

5
88 70 61 96 120

70

Limitation

1s, 1024KiB for each test case.