$N$ students want to pick up a worksheet from the teacher's desk. It takes student $i$ $t_i$ seconds to reach the desk and $1$ second to pick up the worksheet. However, while one student is picking up a worksheet, no other student can pick one up.

Ignoring the time it takes to return to their seats after picking up the worksheet, find the minimum time in seconds required for all students to finish picking up their worksheets.

Input

The first line contains the number of students $N$. $(1 \le N \le 1\,000)$

The second line contains $N$ integers $t_1, t_2, \dots, t_N$ separated by spaces, representing the time it takes for each student to reach the desk. $(1 \le t_i \le 10^5)$

Output

Output the minimum time in seconds required for all students to pick up their worksheets.

Examples

Input 1

5
3 1 2 4 2

Output 1

6