Mua sắm
Đề bài
Mô tả
Cửa hàng có món hàng được xếp thành một hàng duy nhất. Có khách hàng đã đặt đơn online, mỗi đơn gồm món hàng phân biệt.
Khi xử lý đơn hàng thứ , thu ngân lần lượt lấy các món . Gọi là vị trí (đánh số từ ) của món trong hàng tại thời điểm lấy món đó. Thời gian xử lý đơn bằng .
Ngay sau khi lấy một món ra khỏi hàng, thu ngân đặt một món mới cùng loại lên đầu hàng (món vừa bị lấy được thay bằng bản sao mới ở vị trí , các món còn lại giữ nguyên thứ tự tương đối). Cửa hàng có nguồn cung vô hạn.
Hãy tính tổng thời gian xử lý toàn bộ đơn hàng.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên , , .
- Dòng thứ hai chứa số nguyên phân biệt là vị trí ban đầu của các món hàng (món hàng được đánh số từ đến ).
- Mỗi dòng trong dòng tiếp theo chứa số nguyên phân biệt — đơn hàng của khách thứ .
Dữ liệu ra
In ra một số nguyên duy nhất — tổng thời gian xử lý tất cả các đơn hàng.
Ràng buộc
- , các phân biệt
- , các trong cùng một đơn phân biệt
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 5 3 4 1 2 5 1 5 3 1 |
14 | Khách 1 lấy món 1 (vị trí 3), hàng thành ; rồi lấy món 5 (vị trí 5), hàng thành . Tốn . Khách 2 lấy món 3 (vị trí 3), hàng thành ; rồi lấy món 1 (vị trí 3), hàng thành . Tốn . Tổng . |
| 3 2 3 3 1 2 1 2 2 1 2 3 |
13 | Ba khách lần lượt mua , , trên cửa hàng có 3 món. |
Bình luận