Points:
1500
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Cho số nguyên dương \(N\) và dãy số có \(N\) số nguyên \(a_1,a_2,...,a_N\).
Ta sẽ xét dãy \(b = (b_1,b_2,...,b_N)\) và dãy \(c = (c_1,c_2,...,c_N)\) như sau:
- Với mỗi \(1 \le i \le N\) thì \(a_i = b_i + c_i\).
- \(b\) là dãy không giảm. Có nghĩa là \(b_i \le b_{i+1}\) với mọi \(1 \le i \le N-1\).
- \(c\) là dãy không tăng. Có nghĩa là \(c_i \ge c_{i+1}\) với mọi \(1 \le i \le N-1\).
Yêu cầu: Bạn hãy tạo ra dãy \(b\) và \(c\) thỏa mãn các điều kiện trên sao cho giá trị \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\) là nhỏ nhất có thể.
Input
- Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
- Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_N\) \((-10^9 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
Output
- In ra giá trị nhỏ nhất có thể của \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 11\).
- Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
3
1 -2 3
Output
10
Note
- \(b\) và \(c\) có thể là các dãy:
- \(b = (0,0,5)\)
- \(c = (1,-2,-2)\).
- Ta sẽ có \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣) = (0+1)+(0+2)+(5+2) = 10\) và \(10\) là giá trị nhỏ nhất có thể. Lưu ý rằng bạn có thể tạo dãy như thế nào cũng được, miễn giá trị là nhỏ nhất đúng yêu cầu đề bài.
Comments