trang chủ / đề bài / icpc21_mn_m

Xếp bài

Đề bài

Mô tả

Ông Bikrone nghĩ ra trò chơi xếp bài một người như sau.

Có n lá bài được xếp thành một hàng, mỗi lá ghi một số: a1,a2,…,an. Ông Bikrone xem lần lượt các lá bài từ trái sang phải và chuyển một số lá về cuối hàng (đầu bên phải). Điều kiện để chuyển một lá bài là bên phải nó có ít nhất một lá bài có giá trị lớn hơn giá trị của nó. Nói chặt chẽ hơn: lá bài ở vị trí i với giá trị ai được chuyển về cuối nếu tồn tại vị trí j (j>i) sao cho aj>ai.

Trò chơi diễn ra theo từng lượt. Trong một lượt, ông xem các lá bài của hàng hiện tại từ trái sang phải; các lá bài được chuyển trong lượt đó lần lượt được đặt về cuối hàng theo đúng thứ tự chúng được xem, còn điều kiện chuyển của mỗi lá chỉ xét các lá bài đứng sau nó trong hàng ở đầu lượt (xem giải thích của ví dụ 1). Trò chơi kết thúc khi ông Bikrone không thể chuyển thêm lá bài nào về cuối hàng.

Yêu cầu: Hãy giúp ông Bikrone tính tổng số lần chuyển bài cần thực hiện cho đến khi trò chơi kết thúc.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n: số lá bài.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an cách nhau bởi dấu cách: giá trị các lá bài theo thứ tự ban đầu từ trái sang phải.

Dữ liệu ra

In ra một số nguyên: tổng số lần chuyển bài cần thực hiện để kết thúc trò chơi.

Ràng buộc

  • 1≤n≤106.
  • 1≤ai≤109.

Ví dụ

Input Output Giải thích
10
3 7 6 8 5 8 2 1 7 6
14 Lượt 1 chuyển các lá 3,7,6,5,2,1 (6 lần), hàng thành 8,8,7,6,3,7,6,5,2,1. Lượt 2 chuyển 6,3 (2 lần), hàng thành 8,8,7,7,6,5,2,1,6,3. Lượt 3 chuyển 5,2,1 (3 lần), hàng thành 8,8,7,7,6,6,3,5,2,1. Lượt 4 chuyển 3 (1 lần), hàng thành 8,8,7,7,6,6,5,2,1,3. Lượt 5 chuyển 2,1 (2 lần), hàng thành 8,8,7,7,6,6,5,3,2,1. Tổng cộng 6+2+3+1+2=14.
6
1 2 3 4 5 6
15 Ví dụ bổ sung. Lượt đầu chuyển 5 lá, hàng thành 6,1,2,3,4,5; các lượt sau chuyển lần lượt 4,3,2,1 lá.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0