Thu Thập Số

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một hoán vị của các số $1, 2, \dots, n$ . Bạn muốn thu thập các số theo thứ tự tăng dần (từ $1$ đến $n$ ) bằng cách thực hiện nhiều lượt. Mỗi lượt, bạn duyệt mảng từ trái sang phải và thu thập số tiếp theo cần lấy nếu gặp nó.

Hỏi cần ít nhất bao nhiêu lượt để thu thập tất cả các số?

Dữ liệu vào

Dòng 1: số nguyên $n$
Dòng 2: $n$ số nguyên — hoán vị của $1, 2, \dots, n$

Dữ liệu ra

In ra một số nguyên — số lượt tối thiểu.

Ràng buộc

$1 \leq n \leq 2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
5 4 2 1 5 3	3	Lượt 1: duyệt trái→phải, lấy 1. Lượt 2: duyệt lại, lấy 2 rồi 3. Lượt 3: duyệt lại, lấy 4 rồi 5.
3 1 2 3	1	Duyệt một lần lấy được 1, 2, 3 theo thứ tự.

Bình luận

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