Minimum Operations to Reduce Array

You are given an array of n integers. In one operation, you can choose any two elements a_i and a_j (with 1 ≤ i < j ≤ n) such that either a_i \mid a_j or a_j \mid a_i (i.e. either a_i % a_j == 0 or a_j % a_i == 0). When this condition holds, you delete the larger element from the array.

Your task is to determine the minimum number of operations required to reduce the array to a single element. Operations can be performed in any order.

Note: Make sure your solution is efficient enough to handle relatively large inputs.

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers, the elements of the array.

outputFormat

Output a single integer representing the minimum number of operations required to reduce the array to a single element.

## sample

4
2 3 6 9

2

</p>