Gửi bài giải


Điểm: 0,56 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
ONI 2005
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.

  1. Khởi tạo danh sách ~Q =~ rỗng;
  2. Lần lượt thực hiện các biến đổi ~X_i~, ~1 \le i \le 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~;
  3. Mô tả ~X_i~: Khi bắt đầu thực hiện ~X_i~, ~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 ~X_i~ khi đó bằng ~K \times i~;
  4. 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 ~X_1, X_2, \dots, X_N~.

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~.

~\begin{array}{l|l|l|l|l} \mbox{Bước} & \mbox{Mô tả} & P & Q & \mbox{Trọng số} \\ \hline 1 & \mbox{Xoá phần tử thứ}\, 3 & 4\, 1\, 2 & 3 & 3 \\ 2 & \mbox{Xoá phần tử thứ}\, 1 & 1\, 2 & 3\, 4 & 2 \\ 3 & \mbox{Xoá phần tử thứ}\, 2 & 1 & 2\, 3\, 4 & 6 \\ 4 & \mbox{Xoá phần tử thứ}\, 1 & - & 1\, 2\, 3\, 4 & 4 \end{array}~

Trọng số của cách sắp xếp là ~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 \leq N \leq 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

Sample Output

15

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.