Find Hash (Distinct Hash Values)

For each position you may freely choose a non-negative secretKey, giving hash[i]=secretKey[i] mod param[i]. Find the maximum number of distinct values in the hash array.

输入格式

The first line contains n (1..200000), and the second line contains n param values (1..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

3
1 2 4

输出：

3

样例 2

输入：

2
1 1

输出：

1

样例 3

输入：

1
3

输出：

1

样例说明

Example 1: remainders 0, 1, 2 can be chosen, 3 in total. Example 2: modulo 1 can only give 0, so there is 1 value. Example 3: there is only one position, so at most 1 value.