Cho một dãy gồm ~n~ ô, mỗi ô có ~a_i~ viên kẹo.

Bạn có thể thao tác trên các ô như sau: lấy hai cái kẹo ở ô ~x~ và bỏ vào ô ~x-1~ một cái kẹo. Hãy cho biết số kẹo lớn nhất ô ~a_1~ có thể có là bao nhiêu.

Input

• Dòng đầu gồm số tự nhiên ~n~ (~1 \le n \le 10^5~) - là số ô của dãy.

• Dòng thứ hai gồm ~n~ số tự nhiên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~) - là số kẹo từng ô.

Output

• Một dòng duy nhất là số kẹo lớn nhất ô ~1~ có thể có.

Scoring

Sample Input 1

3
2 1 2

Sample Output 1

3