Cho một lưới ô vuông và một điểm A xuất phát tại ô (0, 0). Điểm A chỉ được di chuyển sang phải hoặc đi lên.

Cho n số nguyên dương d₁, d₂, …, dₙ. Với mỗi khoảng cách dᵢ, A có thể thực hiện một bước di chuyển dᵢ đơn vị: từ (x, y) đến (x + dᵢ, y), hoặc từ (x, y) đến (x, y + dᵢ). Mỗi dᵢ chỉ được sử dụng tối đa một lần; có thể chọn thứ tự sử dụng các khoảng cách. Trong một bước, A đi qua các ô nằm giữa vị trí xuất phát và vị trí kết thúc.

Hãy xác định tổng số ô khác nhau mà A có thể đi qua hoặc đến được, tính cả ô (0, 0), xét trên tất cả các cách di chuyển hợp lệ.

Dữ liệu vào

Dòng đầu chứa n (1 ≤ n ≤ 100).

Dòng thứ hai chứa n số nguyên dương d₁, …, dₙ, với tổng dᵢ ≤ 10⁶.

Kết quả

Một số nguyên là số ô cần tìm.

Ví dụ

Input

2
4 2

Output

22

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.