Trong đêm tối một nhóm N người lữ hành muốn vượt qua sông một cách nhanh nhất nhờ một cái cầu nhỏ bắc ngang sông. Do cái cầu quá hẹp và cũ kỹ nên đồng thời chỉ có thể cho phép hai người đi trên cầu. Mặt khác để đảm bảo an toàn khi vượt qua cầu cần phải dùng đèn pin để chiếu sáng đường đi, mà đoàn lữ hành này chỉ có một cái đèn pin.
Một người lữ hành cần thời gian ti để đi qua cầu, i=1,2,...,N (N là số nguyên dương không quá 100). Nếu hai người lữ hành cùng vượt sông thì thời gian qua cầu sẽ là thời gian của người đi chậm hơn.
Yêu cầu: Hãy xác định thời gian vượt sông nhanh nhất
Dữ liệu nhập:
- Dòng đầu là số nguyên N
- Dòng thứ hai chứa các số nguyên t1, t2, ..., tn.
Kết quả ra:
- Thời gian qua sông nhanh nhất tìm được.