← 返回题目列表

Codeforces · 1165/B

B. 波利卡普训练

中文机器翻译题面 查看原题

Polycarp 想要在另一场编程比赛之前进行训练。在训练的第一天,他应该准确地解决 $$$1$$$ 问题,在第二天 - 准确地解决 $$$2$$$ 问题,在第三天 - 准确地解决 $$$3$$$ 问题,等等。在第 $$$k$$$ 天里,他应该解决 $$$k$$$ 问题。

Polycarp 有一个 $$$n$$$ 竞赛列表,第 $$$i$$$ 竞赛包含 $$$a_i$$$ 问题。波利卡普每天必须从他尚未解决的比赛中准确选择一场并解决它。他准确地解决了本次比赛中的 $$$k$$$ 问题。其他问题将被排除。如果在第 $$$k$$$ 天期间没有包含至少 $$$k$$$ 问题的竞赛,Polycarp 尚未解决,则 Polycarp 停止训练。

如果选择最佳的比赛,波利卡普可以训练多少天?

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 比赛数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 第 $$$i$$$ 次竞赛中的问题数。

输出

打印一个整数——如果波利卡普选择最佳比赛,他可以训练的最大天数。

示例

输入 #1

4
3 1 4 1

输出 #1

3

输入 #2

3
1 1 1

输出 #2

1

输入 #3

5
1 1 1 2 2

输出 #3

2