1632D - New Year Concert - CodeForces Solution

from sys import stdin , setrecursionlimit
input = stdin.readline

inp = lambda : list(map(int,input().split()))

class sparsetable:

    def __init__(self , function , bound):
        self.b = None
        self.block = None
        self.n = None
        self.size = None
        self.bound = bound
        self.function = function

    def construct(self , a):

        self.n = len(a)
        for i in range(30):
            if(self.n < (1 << i)):
                self.size = i
                break

        self.b = [[self.bound for i in range(self.size)] for j in range(self.n)]
        self.block = [-1 for i in range(self.n + 1)]

        for i in range(self.n):
            self.b[i][0] = a[i]
        
        for j in range(1 , self.size):
            for i in range(self.n - (1 << (j - 1))):
                self.b[i][j] = self.function(self.b[i][j - 1] , self.b[i + (1 << (j - 1))][j - 1])
        
        for i in range(1 , self.n + 1):
            for j in range(self.size - 1 , -1 , -1):
                if(i >= (1 << j)):
                    self.block[i] = j
                    break

    def query(self , l , r):

                dist = r - l + 1

        ans = self.function(self.b[l][self.block[dist]] , self.b[r - (1 << self.block[dist]) + 1][self.block[dist]])
        return ans
        
    
    def log_query(self , l , r):

                dist = r - l + 1

        ans = self.bound
        for i in range(self.size - 1 , -1 , -1):
            if(dist >> i & 1):
                ans = self.function(ans , b[l][i])
                l += (1 << i)

        return ans

def gcd(a , b):
    if(b == 0):return a
    return gcd(b , a % b)

def answer():

    b = sparsetable(gcd , 0)
    b.construct(a)
    
    ans , done = 0 , -1
    for i in range(n):
 
        l , h = 1 , i - done
        while(l <= h):
            mid = (l + h)//2
            g = b.query(i - mid + 1 , i)
 
            if(g == mid):
                done = i
                ans += 1
                break
                
            if(g > mid):l = mid + 1
            else:h = mid - 1
            
        print(ans , end = ' ')
    
 
for T in range(1):
 
    n = int(input())
    a = list(map(int,input().split()))
    
    answer()