F. Lazy Hash Table
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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 a1, a2, ..., an 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, a1 goes to bucket h(a1), a2 goes to bucket h(a2) 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.

Input

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 a1, a2, ..., an (1 ≤ ai ≤ 2 000 000). It is guaranteed that all elements of sequence a are distinct.

Output

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

Examples
Input
3
1 2 3
Output
3
Input
3
1 2 4
Output
4
Input
5
1 3 6 10 15
Output
8