Cường và Khôi đang chơi một trò chơi với những viên đá. Tuy nhiên trò chơi sau sẽ là trò chơi đồng đội.

Ban đầu có \(N\) tụ đá. Tụ đá thứ \(i\) có \(A_i\) hòn đá.

Trong mỗi lượt Cường lẫn Khôi phải chọn cho mình một tụ đá để lấy một hòn đá từ tụ đã chọn sao cho hai tụ đá đó phải khác nhau và phải có ít nhất \(1\) hòn đá. Nói cách khác Cường sẽ lấy \(1\) hòn đá từ tụ thứ \(i\), Khôi lấy \(1\) hòn đá từ tụ thứ \(j(i \ne j; A_i,A_j \geq 1)\).

Yêu cầu: Cho \(N\) tụ đá, hỏi Cường và Khôi mỗi người được nhiều nhất bao nhiêu hòn đá?

Input

• Dòng thứ nhất ghi 1 số nguyên dương \(N\) cho biết số tụ đá.
• \(N\) dòng tiếp theo, dòng thứ \(i\) ghi 1 số \(A_i\) duy nhất cho biết số hòn đá ở tụ thứ \(i\).

Output

• Ghi ra số hòn đá nhiều nhất mà mỗi người có.

Constraints

• \(1 \leq N \leq 10^3\)
• \(1 \leq A_i \leq 10^9\)

Example

3
1
2
1 

2