A2650 | $Lemonade Line S$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

这是农场上一个炎热的夏日，Farmer John要给他的$N$头奶牛发柠檬汽水了！所有的$N$头奶牛（方便起见，编号为$1 \dots N$）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体地说，奶牛$i$为了获得柠檬汽水最多愿意排在$w_i$头奶牛之后。现在所有的$N$头奶牛都在田里，但是只要Farmer John敲响牛铃，这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达，但是没有两头奶牛会在同一时刻到达。此外，当奶牛$i$到达时，当且仅当至多有$w_i$头奶牛在排队时她会来排队。 Farmer John想要提前准备一定量的柠檬汽水，但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。

第一行包含$N$，第二行包含$N$个用空格分隔的整数$w_1, w_2, \dots, w_N$。输入保证$1 \leq N \leq 10^5$，此外对于每头奶牛$i$，$0 \leq w_i \leq 10^9$。

输出在所有可能的奶牛到达顺序之下，最小可能的排队的奶牛数量。

输入 #1

5
7 1 400 2 2

输出 #1

C++ 编辑器

输入

输出