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 \leq i \leq n)\) dự định thi đấu đúng \(s_i\) \((1 \leq s_i \leq 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, ..., 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, ..., s_n\).

Output

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

Scoring

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

Example

2
2 2

1