Khôi phục đoạn

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
huyhau6a2
Dạng bài
Đ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 đố huyhau6a2 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ì huyhau6a2 sẽ tặng cho các bạn một món quà đặc biệt đấy. Hãy giúp huyhau6a2 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 2
Output 
4

Test 2

Input 
7
4 3 2 0 2 3 3
Output 
7

Bình luận


  • 3
    huyhau6a2    8:11 a.m. 20 Tháng 1, 2022 ← chỉnh sửa 2
    • Hint: Bạn có thể ac bài này trong O(n) không?
    • Bài này là bài lừa thôi, ai ac bài này chắc chắn là pro lqdoj, không khó đâu nha(phần thưởng mình sẽ tặng cho các bạn là ac thêm 1 bài và thêm điểm hehehhe)
    • 1 bình luận nữa