Задача . D. Новогодний концерт

Новый год совсем близко, а это значит, что в 179-й школе уже полным ходом идет подготовка к новогоднему концерту.

Всего в школе есть \(n\) классов, пронумерованных целыми числами от \(1\) до \(n\), \(i\)-й класс подготовил сценку продолжительностью \(a_i\) минут.

Иднар, как главный за проведение новогоднего концерта, знает, что если на концерте будет \(k\) сценок продолжительностями \(b_1\), \(b_2\), \(\ldots\), \(b_k\) минут, то зрителям станет скучно, если найдутся \(l\) и \(r\) такие, что \(1 \le l \le r \le k\) и \(\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1\), где \(\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)\) обозначает наибольший общий делитель (НОД) чисел \(b_l\), \(b_{l + 1}\), \(\ldots\), \(b_{r - 1}\), \(b_r\).

Чтобы во время концерта зрителям не стало скучно, Иднар может сколько угодно раз (возможно, ноль) попросить \(t\)-й класс (\(1 \le t \le k\)) сделать другую сценку продолжительностью \(d\), где \(d\) может быть любым целым положительным числом. Таким образом, после данной операции \(b_t\) станет равно \(d\). Заметьте, что \(t\) и \(d\) для разных операций могут быть различными.

Для последовательности продолжительностей сценок \(b_1\), \(b_2\), \(\ldots\), \(b_{k}\) определим функцию \(f(b)\) как минимальное количество классов, у которых Иднар должен попросить заменить сценку, чтобы зрителям не стало скучно.

Иднар еще точно не определился, какие сценки будут допущены на концерт, поэтому хочет узнать значение функции \(f\) от каждого из непустых префиксов \(a\). Иными словами, Иднар хочет узнать значения \(f(a_1)\), \(f(a_1\),\(a_2)\), \(\ldots\), \(f(a_1\),\(a_2\),\(\ldots\),\(a_n)\).