Cho dãy số nguyên A gồm N phần tử a1, A2, ..., AN. Giá trị của dãy số A được tính như sau:
Ví dụ dãy số A: 6, 2, 1,3. Ta có v (A) = |6 - 1| + |2 - 2| + |1 - 3| + |3 - 4| = 8.
Cho thao tác quay vòng mảng A được thực hiện như sau: chuyển số ở vị trí cuối cùng lên vị trí đầu tiên: a1, a2,., aN-1, aN → aN, a1, a2, .., aN-1
Ví dụ dãy số A: 6, 2, 1, 3, sau một thao tác quay vòng thì dãy số sẽ như sau: 3, 6, 2, 1.
Yêu cầu: cho dãy số A, hãy sử dụng thao tác quay vòng một số lần để giá trị của dãy số lớn nhất.
Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:
Dòng đầu tiên gồm một số nguyên dương N (N ≤ 10^5);
Dòng thứ hai gồm N số nguyên a1, a2, ..., aN-1, aN (|ai| ≤ 10^9;1 ≤ i ≤ N).
Kết quả: Ghi ra thiết bị ra chuẩn gồm một số nguyên là giá trị của dãy số lớn nhất tìm được.
Ràng buộc:
Có 40% số test ứng với 40% số điểm của bài có N ≤ 10^3;
30% số test khác ứng với 30% số điểm của bài có N ≤ 10^5; ai ≤ ai+1 Với 1 ≤ i < N;
30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.
Input:
4
6 2 1 3
Output:
10
Giải thích:
Ban đầu dãy số 6,2,1,3 có giá trị là 8;
Quay vòng dãy số trên ta có dãy số: 3,6,2,1 có giá trị là 10
Quay vòng dãy số trên ta có 1,3,6,2 có giá trị là 6
Quay vòng dãy số trên ta có dãy số 2,1,3,6 có gí trị là 4
Vậy giá trị lớn nhất tìm được là 10
Bình luận