Khôi phục đoạn

Xem PDF
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


  • 1
    huyhau6a2    8:34 a.m. 20 Tháng 1, 2022 ← đã chỉnh sửa
    • Ai không hiểu đề nhớ comment giúp mình nha
    • Giải thích Test 1:
      . . .
      ___
      ___ ___
      _________
    • Dấu 3 chấm ở trên chỉ 3 điểm thuộc trục Ox, các đoạn thẳng cần vẽ trên tượng trưng cho các đoạn thẳng cần khôi phục
    • Giải thích test 2:
      . . . . . . .
      ___
      ______ ______
      _________ _________
      _________ _________
    • Dấu 7 chấm ở trên chỉ 7 điểm thuộc trục Ox, các đoạn thẳng cần vẽ trên tượng trưng cho các đoạn thẳng cần khôi phục
    • Ai phát hiện ra quy luật bài này sẽ ac nha

    • 1
      nguyendanghau2006    11:13 a.m. 22 Tháng 1, 2022

      bạn có thể giải thích test đề được ko 🙂


    • 1
      PhanHuyKhang    2:04 p.m. 20 Tháng 1, 2022 ← đã chỉnh sửa

      à thôi, mik hiểu r


      • 2
        dang7rickroll    9:30 a.m. 20 Tháng 1, 2022

        Đã AC, thanks bạn đã cho hint.


        • 2
          huyhau6a2    9:45 a.m. 20 Tháng 1, 2022

          Phần thưởng đã được lqdoj gửi về là 1 bài ac và thêm điểm nha bạn

        1 bình luận nữa