[submission:257656771][problem:1547F] The Maximum Number of Operation we Need is N : so we do binary search On ans the element at ith index at kth step will be gcd of range (i,k) for range gcd i used segTree.

int n ;
	cin >> n  ;
	vector<int> a(2 * n);
	for (int i = 0 ; i < n ; i++) {
		cin >> a[i];
	}
	for (int i = 0 ; i < n ; i++) {
		a[n + i] = a[i];
	}
	int temp = 2 * n ;
	int temp2 = 2 * n ;
	while ((temp2) & (temp2 - 1)) {
		temp2++;
		a.pb(0);
	}
	vector<int> seg(2 * temp2);
	for (int i = 0 ; i < temp2 ; i++) {
		seg[temp2 + i] = a[i];
	}
	for (int i = temp2 - 1 ; i >= 1; i--) {
		seg[i] = __gcd(seg[2 * i], seg[2 * i + 1]);
	}
	auto query = [&](int l , int r) {
		l += temp2;
		r += temp2;
		int ans = 0 ;
		while (l < r) {
			if (l & 1) ans = __gcd(ans, seg[l++]);
			if (r & 1) ans = __gcd(ans, seg[--r]);
			l /= 2; r /= 2;
		}
		return ans ;
	};
	debug(a);
	auto check = [&](int mid) {
		set<int> s ;
		for (int i = 0 ; i < n ; i++) {
			int r = i + mid + 1  ;
		// 	cout << i << " " << r << " " << query(i, r) << endl;
			s.insert(query(i, r));
		}
		return (s.size() == 1);
	};
	int lo = 0 ;
	int hi = n  ;
	int ans = 0 ;
	while (lo <= hi) {
		int mid  =  (hi + lo) / 2 ;
		if (check(mid)) {
			ans = mid ;
			hi = mid - 1 ;
		}
		else {
			lo = mid + 1 ;
		}
	}
	cout << ans << endl;