Chơi đá 2

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

CườngKhô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\)\(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ườngKhô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

Test 1

Input
3
1
2
1 
Output
2
Note
  • Lượt \(1:\) Cường lấy ở tụ \(1\), Khôi lấy ở tụ \(2\).
  • Lượt \(2:\) Cường lấy ở tụ \(2\), Khôi lấy ở tụ \(3\).

Bình luận