Description

下课啦~每到中午食堂的窗口就异常的拥挤，为了缓解学生们吃饭的时候造成的交通堵塞，小A在想如何选择窗口，对此他提出了要求：

• 备选食堂窗口个数为奇数，则选择排队人数居中的窗口
• 备选食堂窗口个数为偶数，存在排队人数居中的两个窗口 $w_i, w_{i + 1}$ ，选择其窗口人数较少的一个

请帮小A分析现状：食堂的 $n$ 个窗口选哪个最合适，并输出将要排在小A前面的人数。

众所周知没人排队的窗口饭菜可能会不可口，所以小A不会将没人排队的窗口放在备选窗口方案中

Input Format

每个测试用例的第一行包含一个整数：$n(1 \le n \le 5000)$ 表示窗口个数。

第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n(0\le w_i \le 10^5)$ 表示第 $i$ 个窗口的排队学生个数。

Output Format

输出共一行，为小A选择的窗口排队人数。

4
0 3 2 1​

2​

4​
1 2 3 4​

2

Hint