Linh tìm thấy \(N\) chuỗi trên gác nhà mình. Mỗi chuỗi bao gồm một dãy các vòng tròn nối với nhau.

Linh muốn nối các chuỗi trên lại thành một chuỗi dài bằng cách mở một số vòng tròn trên các chuối sau đó luồn nó nối với vòng tròn khác và hàn lại. Hỏi rằng Linh cần mở ít nhất bao nhiêu vòng tròn để có thể làm được điều này?.

Input

• Dòng đầu tiên ghi \(N\) là số lượng chuỗi tìm được (\(2 \le N \le 10^6\))
• Dòng thứ hai chứa \(N\) số nguyên dương \(L_i\) (\(1 \le L_i\le 10^6\)) là độ dài (số lượng vòng tròn) của các chuỗi.

Output

• Ghi một số nguyên duy nhất là số lượng vòng tròn phải mở

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^4\).
• Subtask \(2\) (\(25\%\) số điểm): \(n ≤ 10^6\).

Example

2
3 3 

1

5
4 8 5 7 9 

4