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)