задача на C++, помогите решить , пожалуйста

Вам дан массив a размера n. Пара чисел (i, j) называется дружественными, если a_i делится на a_j, или a_j делится на a_i.

Разбейте a на максимальное количество блоков так, чтобы для каждой пары дружественных чисел, оба числа находились в одном и том же блоке. Блок — это подотрезок.

Входные данные

В первой строке находится одно целое число n (1 ≤ n ≤ 3⋅10⁵).

Во второй строке находятся n целых чисел a₁, a₂, ... , a_n (1 ≤ a_i ≤ 3⋅10⁵).

Выходные данные

Выведите ответ на задачу.

Примеры

входные данные

4
2 3 4 5

выходные данные

2

входные данные

3
2 1 4

выходные данные

1