Đ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.

Đầu vào:

Dòng đầu tiên chứa một số nguyên

Dòng thứ hai chứa n số nguyên

Đầu ra:

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

Ràng buộc:

1 ≤ n ≤ 2.10^5

0 ≤ ai ≤ 10^9

Ví dụ:

Input:

3
1 2 1

Output:

2