405191: GYM101821 F Lazy Hash Table

Yandex engineer Ivan is a very tidy person, he is among people who always create an array of size exactly they need.

Today Ivan has n distinct positive integers a₁, a₂, ..., a_n he would like to put in a hash table. He wants to pick some integer m — the number of buckets and then send integer x to bucket . So, a₁ goes to bucket h(a₁), a₂ goes to bucket h(a₂) and so on. As much as Ivan loves order, Ivan hates collisions. He wants to pick m in such a way that each bucket contains at most one integer. In other words, Ivan wants to choose m such that all are distinct. Please find such m. As one of the goals of a data infrastructure engineer is to be as efficient as possible, Ivan wants you to find minimum possible valid value of m.

The first line of the input contains one integer n (1 ≤ n ≤ 2 000 000) — the number of integers Ivan possesses. The next line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 2 000 000). It is guaranteed that all elements of sequence a are distinct.

Print one integer — the minimum possible value of m such that all values will be distinct.

3
1 2 3

3

3
1 2 4

4

5
1 3 6 10 15

8