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

Cho dãy P gồm N số hạng khác nhau từng đôi, các số hạng có giá trị trong phạm vi 1..N. Một cách sắp xếp dãy này thành dãy đơn điệu tăng diễn ra như sau.

- Khởi tạo danh sách Q = rỗng;

- Lần lượt thực hiện các biến đổi XI, 1 <= I <=N, sao cho sau dãy biến đổi này, trong danh sách Q ta nhận được dãy 1, 2, 3, . . ., N;

- Mô tả XI: Khi bắt đầu thực hiện XI, P có N-I+1 số hạng, Q có I-1 số hạng. Xoá một số hạng của P, chẳng hạn số hạng thứ K và chọn việc viết tiếp số hạng đó vào bên trái hay bên phải danh sách Q; Trọng số của biến đổi XI khi đó bằng K x I;

- Trọng số của cách sắp xếp bằng tổng các trọng số của của N biến đổi X1, X2, ..., XN.

Ví dụ, nếu P là dãy 4 1 3 2 Bảng sau cho ta một cách sắp xếp dãy P.

Bước	Mô tả	                P	Q	Trọng số
1	Xoá phần tử thứ 3	4 1 2	3	3
2	Xoá phần tử thứ 1	1 2	3 4	2
3	Xoá phần tử thứ 2	1	2 3 4	6
4	Xoá phần tử thứ 1	-	1 2 3 4	4

Trọng số của cách sắp xếp = 15

Cho dãy P, hãy tìm một cách sắp xếp P thành dãy Q đơn điệu tăng có trọng số nhỏ nhất.

Input

- Dòng thứ nhất ghi số N, 1 ≤ N ≤ 1000.

- Trong một số dòng tiếp theo ghi lần lượt N số hạng của dãy P.

Output

Ghi trọng số của cách sắp xếp nhỏ nhất.

Sample

input 
4 
4 1 
3 
2

output 
15