Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT127F - Xếp sách

Có N quyển sách, đánh nhãn đôi một khác nhau từ 1 đến N xếp ngẫu nhiên trên một chồng. Bạn cần sắp xếp lại chồng sách theo thứ tự nhãn từ 1 đến N (tính từ đỉnh của chồng sách). Mỗi lượt di chuyển, bạn chỉ có thể lấy ra một quyển sách và đặt nó lên đỉnh của chồng sách.

Ví dụ: Nếu N=3, và thứ tự nhãn từ đỉnh ban đầu của chồng sách là {3,2,1}, bạn có thể lấy ra cuốn có nhãn là 2 và đặt lên đầu, chồng sách trở thành {2,3,1}. Tiếp theo, lấy cuốn có nhãn là 1, và đặt lên đầu, chồng sách trở thành {1,2,3}.

Nhiệm vụ của bạn là tìm xem cần tối thiểu bao nhiêu lượt di chuyển.

Input

Dòng 1: Số N (N ≤ 300 000)

N dòng tiếp theo, mỗi dòng chứa một số nguyên dương là nhãn của cuốn sách, dòng thứ i là nhãn của cuốn sách thứ i tính từ đỉnh.

Output

Số lần di chuyển tối thiểu

Example

Input:
3

3

2

1

Output: 2
Input:

4

1

3

4

2

Output: 2

Được gửi lên bởi:adm
Ngày:2012-03-31
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2020-12-26 06:32:12
Bài này mng nộp ngôn ngữ CPP14 ấy :v
2020-04-24 06:07:15
Tham khảo: https://github.com/ManhLk/SVMC/blob/master/Xep_sach.cpp
2020-03-22 08:53:33
toan bi qua tg nhi
2017-07-26 12:03:37
PTIT127F: https://e16cn-ptit.blogspot.com/2017/12/ptit127f-xep-sach.html

Last edit: 2017-12-12 10:56:48
2016-07-02 04:55:14
1 đấm ac

2015-07-04 14:26:32 Nguyễn Ðình Vinh
quicksort đc k nhỉ ??
2013-08-05 12:07:59 Nhớ Nguồn
Chỉ load xong dữ liệu là in ra luôn mà cũng mất hơn 1s, không hiểu các bạn 0.5s làm kiểu gì nữa @@
2013-08-05 09:40:09 phantom assassin
nghe đại ca Huấn chuyển thành scanf thế là dk, cơ mà lúc chưa xóa cái using namespace std; thì lại kq sai là sao nhỉ :(
2012-11-07 04:02:03 ctk41
ai biet thuat toan' khong
2012-09-15 15:34:14 Vương Sỹ Huấn DH BK TP HCM
thay moi cin thanh scanf ma lai dat yeu cau kho hieu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.