Cho 1 dãy gồm N (1<=N<=2000) số nguyên a1,a2,..,an(0<=Ai<=1 000 000 000). Hãy tìm 1 dãy B không tăng hoặc không giảm cũng gồm n số nguyên b1,b2,...,bn sao cho
S=[A1-B1]+[A2-B2]+...+[An-Bn] đạt giá trị nhỏ nhất ( dấu [] là trị tuyệt đối)
Inp
Dòng 1 : số N
N dòng tiếp theo, dòng thứ i ghi số Ai
Out
Số S nhỏ nhất tìm được( ko cần in ra dãy B)
VD
Inp
7
1
3
2
4
5
3
9
Out
3
Thêm: dãy B của cái vd trên là 1 2 2 4 4 4 9
Không tăng hoặc không giảm nghĩa là đó là dãy tăng hoặc dãy giảm nhưng có ít nhất 2 phần tử bằng nhau