Distinct Integers After Operations

You are given an array of n integers. You are allowed to perform the following operation any number of times (including zero): choose any two different elements a and b from the array and replace the larger one with the absolute difference \(|a-b|\).

After applying these operations optimally, determine the maximum possible number of distinct integers that can be present in the array. It can be proven that regardless of the sequence of operations, the final number of distinct integers will be one of \(1\), \(2\), or \(3\).

Note: The operations allow you to gradually reduce differences between numbers. For example, for an array with only even numbers the process will eventually lead to a single distinct value, while for arrays with odd numbers, additional distinct values may be introduced depending on whether 0 is already present.

inputFormat

The input is provided on two lines. The first line contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer, which is the maximum number of distinct integers that can appear in the array after performing the operations optimally.

## sample

4
1 5 3 9

3

</p>