Khôi phục đoạn
Xem PDF
Điểm:
300
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Vị thần hình học đã thách đố một bài toán như sau:
Cho \(n\) điểm thuộc trục \(Ox\), mỗi điểm được đánh số từ \(1\) đến \(n\). Với điểm thứ \(i\) có \(A_i\) đoạn thẳng chứa điểm đó. Vấn đề vị thần hình học đưa ra là hãy tìm số đoạn thẳng cần khôi phục ít nhất sao cho thỏa mãn tất cả điều kiện trên.
Nếu hoàn thành thử thách thì sẽ tặng cho các bạn một món quà đặc biệt đấy. Hãy giúp nhé!
Input
- Dòng 1 gồm duy nhất 1 số \(n(n \le 10^6)\)
- Dòng 2 gồm \(n\) số chỉ số đoạn thẳng bao hàm của mỗi điểm \((A_i \le 10^9)\)
Output
- Duy nhất 1 số là số đoạn thẳng ít nhất cần khôi phục thỏa mãn
Example
Test 1
Input
3
3 1 2Output
4Test 2
Input
7
4 3 2 0 2 3 3Output
7
Bình luận
. . .
___
___ ___
_________
. . . . . . .
___
______ ______
_________ _________
_________ _________