Tổng chênh lệch

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

AhhShibaaa cung cấp cho bạn dãy số nguyên gồm \(N\) phần tử.

Nhiệm vụ của bạn là thay đổi một vài giá trị trong dãy về bằng \(1\) (hoặc giữ nguyên) sao cho tổng các chênh lệch tuyệt đối giữa \(2\) phần tử liên tiếp là lớn nhất.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 5*10^5)\).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_n ( 1 \le a_i \le 10^6)\)

Output

  • Một số nguyên duy nhất là tổng trị tuyệt đối lớn nhất giữa \(2\) phần tử liên tiếp sau khi biến đổi.

Example

Test 1

Input
3
1 8 9 
Output
14
Note
  • Tổng ban đầu : \(|1 - 8| + |8 - 9| = 8\)
  • Thay đổi : \([1, 8, 9] \rightarrow [1, 8, 1]\)
  • Tổng lúc sau : \(|1 - 8| + |8 - 1| = 14\)

Scoring

  • Subtask \(1\): (30 %) \(n \le 20\)
  • Subtask \(2\): (30 %) \(n \le 10^3\)
  • Subtask \(3\): (40 %) \(n \le 5 * 10^5\)

Bình luận


  • 1
    thanhkhoa123    9:51 p.m. 8 Tháng 6, 2022 đã chỉnh sửa

    Bài không khó nhưng tôi cần tăng bộ nhớ =))))))))))))


    • 0
      thanphong    5:12 p.m. 22 Tháng 3, 2022

      mik vẫn chưa hiểu qhd của bài này lắm


      • 1
        huyhau6a2    4:17 p.m. 16 Tháng 3, 2022

        ai chỉ cho mình bài này được không?

        1 phản hồi