Tạo bài thi đấu

Bối cảnh

Hùng đã tạo ra \(N\) bài toán cho lập trình thi đấu. Các bài toán được đánh số từ \(1\) đến \(N\), và độ khó của Bài toán \(i\) được biểu diễn bằng một số nguyên \(d_i\) (càng cao càng khó).

Yêu cầu

Anh ấy chia các bài toán thành hai hạng mục bằng cách chọn một số nguyên \(K\), như sau:

• Một bài toán có độ khó \(K\) trở lên sẽ thuộc về ARCs.
• Một bài toán có độ khó thấp hơn \(K\) sẽ thuộc về ABCs.

Hỏi có bao nhiêu lựa chọn số nguyên \(K\) sao cho số lượng bài toán cho ARCs và số lượng bài toán cho ABCs như nhau?

Input

N
d_1 d_2 ... d_N

Output

In ra số lượng lựa chọn số nguyên \(K\) sao cho số lượng bài toán cho ARCs và số lượng bài toán cho ABCs như nhau.

Ràng buộc

• \(2 \leq N \leq 10^5\)
• \(N\) là số chẵn.
• \(1 \leq d_i \leq 10^5\)
• Tất cả giá trị đầu vào là số nguyên.

Ví dụ 1

Input

6
9 1 4 4 6 7

Output

2

Giải thích ví dụ

Nếu chọn \(K=5\) hoặc \(6\), Bài toán \(1, 5,\) và \(6\) sẽ thuộc về ARCs, Bài toán \(2, 3,\) và \(4\) sẽ thuộc về ABCs, và mục tiêu được đạt được. Vì vậy, câu trả lời là \(2\).

Ví dụ 2

Input

8
9 1 14 5 5 4 4 14

Output

0

Giải thích ví dụ

• Ví dụ 1: 9 1 4 4 6 7 có hai giá trị K khả dĩ: K = 5 và K = 6, vì chúng phân chia bài toán thành hai nhóm có số lượng bằng nhau.

• Ví dụ 2: 9 1 14 5 5 4 4 14 không có giá trị K nào phân chia bài toán thành hai nhóm có số lượng bằng nhau.

Có thể không có lựa chọn số nguyên \(K\) nào khiến số lượng bài toán cho ARCs và ABCs như nhau.

Thông tin học tập

• Buổi: B16
• Concepts: sorting, median positions
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 25