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

3
1 -2 3

10