Có \(n + 1\) đội bóng, các đội được đánh số từ \(0\) đến \(n\). Đội bóng số \(0\) dự định tổ chức một giải giao hữu và mời \(n\) đội tham gia. Khi tham gia, đội thứ \(i\) \((1 \le i \le n)\) dự định thi đấu đúng \(s_i\) \((1 \le s_i \le n)\) trận. Gọi \(s_0\) là số trận mà đội số \(0\) sẽ thi đấu, dựa vào số liệu đăng kí của mỗi đội, đội số \(0\) muốn biết \(s_0\) có thể nhận những giá trị nào để có thể tổ chức giải đấu với số lượng trận đúng như các đội đã đăng kí mà mỗi cặp đội sẽ đấu với nhau không quá một trận.

Yêu cầu: Cho các số nguyên dương \(s_1, s_2, \dots, s_n\), hãy đếm xem có bao nhiêu giá trị nguyên dương \(s_0\) thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(s_1, s_2, \dots, s_n\).

Output

• Ghi ra một số nguyên là số lượng giá trị \(s_0\) thỏa mãn.

Example

2
2 2

1

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 50000\).
• Subtask \(6\) (\(15\%\) số điểm): \(n \le 500000\).