Giải bài trực tuyến

Một công ty vận tải thuê 1 đoàn tàu hỏa để chở hàng cho khách. Tuy nhiên sau khi đã xếp hàng lên hết thì nhận được thêm yêu cầu từ khách là hàng phải được xếp sao cho toa nặng phải ở phía trước toa nhẹ, nói cách khác là các toa phải được sắp xếp theo vị trí giảm dần về trọng lượng hàng hóa trong toa.

Các toa đã được niêm phong nên không thể chuyển hàng giữa các toa được. Cách duy nhất là yêu cầu nhà ga dùng 1 chiếc cần cẩu để chuyển vị trí các toa. Vị trí các toa được đánh số từ 1 trở đi, bắt đầu từ toa phía trước nhất.

Khi cần cẩu chuyển toa từ vị trí I sang vị trí J, vị trí sắp xếp tương đối giữa các toa còn lại không bị thay đổi. Nếu I > J thì số thứ tự vị trí của các toa giữa J và I-1 sẽ tăng thêm 1. Ngược lại, nếu I < J thì số thứ tự vị trí của các toa giữa I+1 và J sẽ giảm đi 1. Chi phí cho mỗi lần cẩu toa I sang vị trí J là I+J đơn vị giá.

Nhiệm vụ của bạn là tìm cách chuyển hàng sao cho tổng số chi phí là thấp nhất.

Dữ liệu

Dòng đầu tiên gồm 1 số nguyên dương N (2 ≤ N ≤ 1000) là số lượng toa đã được dùng để xếp hàng. Trong N dòng tiếp theo, mỗi dòng gồm 1 số nguyên Si (0 ≤ Si ≤ 1000000) là trọng lượng của toa hàng tương ứng theo thứ tự từ 1 đến N.

Kết quả

Một dòng duy nhất ghi tổng chi phí nhỏ nhất để chuyển các toa theo vị trí yêu cầu của khác hàng.

Ví dụ

Dữ liệu:
5
15
40
1
8
6

Kết quả:
11