Nhiều trò chơi toán học có vẻ khá kỳ lạ với mọi người. Sau đây là một trò chơi như thế: Bạn có \(2N-1\) là bài. Ban đầu, trò chơi chỉ sử dụng \(N\) lá bài. Mặt trước của mỗi lá bài được viết \(1\) số nguyên. Mặt sau của lá bài được viết số \(0\). \(N-1\) lá bài còn lại để trống ở cả \(2\) mặt và sẽ không liên quan tới trò chơi. Bạn đoán \(1\) số trong khoảng từ \(1\) đến \(N\). Trò chơi diễn ra theo quá trình sau:

• Chọn lá bài có số ở mặt trước nhỏ nhất. Nếu có nhiều lá bài như thế, thì chọn lá bài có số ở mặt sau nhỏ nhất. Gọi số ở mặt trước của lá bài được chọn là \(A\) còn số ở mặt sau của lá bài là \(B\). Loại lá bài đó khỏi trò chơi.
• Tiếp tục chọn lá bài có số ở mặt trước nhỏ nhất. Nếu có nhiều lá bài như thế thì chọn lá bài có số ở mặt sau nhỏ nhất. Gọi số ở mặt trước của lá bài được chọn là \(C\) còn số ở mặt sau của lá bài là \(D.\) Loại lá bài đó khỏi trò chơi.
• Chọn 1 lá bài được để trống ở cả 2 mặt. Ở mặt trước của lá bài viết số \(A+C\) và ở mặt sau viết số lớn hơn trong \(2\) số \(B + 1\) and \(D + 1\). Cho lá bài đó vào trò chơi.

Trò chơi kết thúc sau \(N-1\) lần làm như vậy, khi trò chơi chỉ còn đúng 1 lá bài. Nếu số ở mặt sau lá bài trùng với số mà bạn đã đoán thì bạn thắng, nếu không thì bạn thua. Viết 1 chương trình tính toán số cuối cùng được viết ở mặt sau của lá bài cuối cùng này.

INPUT

• Dòng đầu tiên ghi số nguyên \(1 ≤ N ≤ 10^5\). Dòng tiếp theo ghi \(N\) số nguyên - những con số ghi trên mặt trước của mỗi lá bài. Mỗi số nằm trong khoảng từ \(-10^9\) đến \(10^9\).

OUTPUT

• In ra 1 số duy nhất: Câu trả lời cho vấn đề

Ví du

Input

5 
1 2 3 4 5

Output

3

Giải thích

Ban đầu (1 0), (2 0), (3 0), (4 0), (5 0)

Vòng 1: (3 1), (3 0), (4 0), (5 0)

Vòng 2: (6 2), (4 0), (5 0)

Vòng 3: (6 2), (9, 1)

Vòng 4: (15, 3)