CSES - Missing Coin Sum | Tổng xu bị thiếu

Xem PDF

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

Bạn có \(n\) đồng xu với các giá trị nguyên dương. Số tiền nhỏ nhất bạn không thể tạo bằng cách sử dụng một tập hợp con của các đồng xu là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đồng xu.
  • Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của mỗi đồng xu.

Output

  • In một số nguyên: tổng tiền xu nhỏ nhất.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x_i \le 10^9\)

Example

Sample input

5
2 9 1 2 7

Sample output

6


Bình luận