CF1140A.Detective Book

入门

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The ii-th page contains some mystery that will be explained on page aia_i (ai≥ia_i \ge i).

Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page ii such that Ivan already has read it, but hasn't read page aia_i). After that, he closes the book and continues to read it on the following day from the next page.

How many days will it take to read the whole book?

伊万最近买了一本侦探小说。这本书非常有趣,每一页都会引出某种谜题,而该谜题会在后续某页中得到解释。第 ii 页引入的谜题将在第 aia_i 页得到解释(满足 ai≥ia_i \ge i)。

伊万希望完整地读完这本书。每天,他从自己尚未阅读的第一页开始阅读,并按顺序逐页继续阅读,直到他所读到的所有谜题都已被解释、对他而言完全清晰为止(即:不存在任何页面 ii,使得伊万已经读过第 ii 页,但尚未读过第 aia_i 页;此时他便会停止阅读)。之后,他合上书本,并于次日从下一页继续阅读。

问:读完整本书共需要多少天?

输入格式

The first line contains single integer nn (1≤n≤1041 \le n \le 10^4) — the number of pages in the book.

The second line contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (i≤ai≤ni \le a_i \le n), where aia_i is the number of page which contains the explanation of the mystery on page ii.

第一行包含一个整数 nn(1≤n≤1041 \le n \le 10^4)—— 表示书的页数。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(满足 i≤ai≤ni \le a_i \le n),其中 aia_i 表示第 ii 页上的谜题解释所在的页码。

输出格式

Print one integer — the number of days it will take to read the whole book.

输出一个整数——读完整本书所需的天数。

输入输出样例

  • 输入#1

    9
    1 3 3 6 7 6 8 8 9

    输出#1

    4

说明/提示

Explanation of the example test:

During the first day Ivan will read only the first page. During the second day Ivan will read pages number 22 and 33. During the third day — pages 44-88. During the fourth (and the last) day Ivan will read remaining page number 99.

示例测试的解释:

第一天,伊万只阅读第一页;
第二天,伊万阅读第 22 页和第 33 页;
第三天,伊万阅读第 44–88 页;
第四天(也是最后一天),伊万阅读剩余的第 99 页。

输入解题思路,AI测评打分。不知道怎么写?

首页