Đoàn tàu hỏa chở khách du lịch ở một địa điểm nổi tiếng có \(n\) toa, toa thứ i có có \(ai\) người, \(i\) \(=\) \(1\)… \(n\). Khi đến nơi mọi người đều nóng lòng muốn ra. Để tránh ùn tắc và gây lộn xộn trên sân ga cứ mỗi đơn vị thời gian người ta có thể cho tất cả hành khách ở một toa xuống hoặc cho mỗi toa một người xuống.

Hãy xác định thời gian tối thiểu để mọi hành khách xuống được ga.

Dữ liệu:

Output:

• Dòng đầu tiên chứa một số nguyên (\(1 \leq n \leq 10^5\))
• Dòng thứ hai chứa n số nguyên \(a_1\), \(a_2\), …, \(a_n\) (\(0 \leq a_i \leq 10^9\), \(i = 1 \to n\))

Input:

• Một số nguyên là thời gian tối thiểu tính được.

Ví dụ:

Input

3
1 2 1

Output

2