Note the unusual time limit in this problem.

You are given an array A of N positive integers.  
The *power* of a subarray A[L, R] (1≤ L≤ R ≤ N) having size (R-L+1) is defined as \gcd(A_{L}, A_{(L+1)}, \ldots, A_{R}), where \gcd denotes the [greatest common divisor]. 

Your task is to find the maximum *power* of a subarray of size k, for all 1≤ k ≤ N.

A subarray is formed by deleting some (possibly zero) elements from the beginning of the array and some (possibly zero) elements from the end of the array.

------ Input Format ------ 

- The first line contains a single integer T: the number of test cases.
- The first line of each test case contains a positive integer N: the size of array A.
- The second line of each test case contains N positive integers: A_{1},A_{2},A_{3},\ldots,A_{N}.

------ Output Format ------ 

For each test case, output N space-separated positive integers.  
The i^{th} integer should be the maximum power among all subarrays of A with size i.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
5
4
5 5 5 5
4
4 2 3 1
3
6 10 15
5
2 6 3 9 24
5
3 11 7 2 5

----- Sample Output 1 ------ 
5 5 5 5
4 2 1 1
15 5 1
24 3 3 3 1
11 1 1 1 1

----- explanation 1 ------ 
Test case $1$:
- Subarray of size $1$ having maximum power is $[A_{2}]$. Thus, $\gcd(A_{2})=5$.
- Subarray of size $2$ having maximum power is $[A_{3}, A_{4}]$. Thus, $\gcd(A_{3},A_{4})=5$.
- Subarray of size $3$ having maximum power is $[A_{1}, A_{2}, A_{3}]$. Thus, $\gcd(A_{1}, A_{2}, A_{3})=5$.
- Subarray of size $4$ having maximum power is $[A_{1}, A_{2}, A_{3}, A_{4}]$. Thus, $\gcd(A_{1}, A_{2}, A_{3},A_{4})=5$. 

Test case $2$: 
- Subarray of size $1$ having maximum power is $[A_{1}]$. Thus, $\gcd(A_{1})=4$.
- Subarray of size $2$ having maximum power is $[A_{1}, A_{2}]$. Thus, $\gcd(A_{1},A_{2})=2$.
- Subarray of size $3$ having maximum power is $[A_{1}, A_{2}, A_{3}]$. Thus, $\gcd(A_{1}, A_{2}, A_{3})=1$.
- Subarray of size $4$ having maximum power is $[A_{1}, A_{2}, A_{3}, A_{4}]$. Thus, $\gcd(A_{1}, A_{2}, A_{3},A_{4})=1$. 

Test case $3$: 
- Subarray of size $1$ having maximum power is $[A_{3}]$. Thus, $\gcd(A_{3})=15$.
- Subarray of size $2$ having maximum power is $[A_{2}, A_{3}]$. Thus, $\gcd(A_{2},A_{3})=5$.
- Subarray of size $3$ having maximum power is $[A_{1}, A_{2}, A_{3}]$. Thus, $\gcd(A_{1}, A_{2}, A_{3})=1$.

Note that there can be multiple subarrays with the same power.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
import sys
input = sys.stdin.readline
from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * (n + 1)
	gcds = {}
	sm = 0
	for x in a:
		new_gcds = {x: 1}
		for g in gcds.keys():
			G = gcd(x, g)
			if G not in new_gcds:
				new_gcds[G] = gcds[g] + 1
			else:
				new_gcds[G] = max(new_gcds[G], gcds[g] + 1)
		gcds = new_gcds
		for g in gcds.keys():
			ans[gcds[g]] = max(ans[gcds[g]], g)
	print(*ans[1:])


from typing import List, Tuple, Dict
import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	gcds = [{} for _ in range(n)]
	for i in range(n):
		gcds[i][a[i]] = 1
		if i:
			for j in gcds[i - 1]:
				new_gcd = math.gcd(j, a[i])
				if new_gcd in gcds[i]:
					gcds[i][new_gcd] = max(gcds[i][new_gcd], gcds[i - 1][j] + 1)
				else:
					gcds[i][new_gcd] = gcds[i - 1][j] + 1
	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in gcds[i]:
			ans[gcds[i][j] - 1] = max(ans[gcds[i][j] - 1], j)
	print(*ans)
t = int(input())
for test in range(1, t + 1):
	solve()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	mp = {}
	for i in range(n):
		ex = arr[i]
		gmp = {}
		gmp[ex] = i
		for (val, left) in mp.items():
			nval = math.gcd(val, ex)
			if nval not in gmp:
				gmp[nval] = left
			else:
				gmp[nval] = min(gmp[nval], left)
		for (val, left) in gmp.items():
			ans[i - left] = max(ans[i - left], val)
		mp = gmp
	for i in range(n - 2, -1, -1):
		ans[i] = max(ans[i], ans[i + 1])
	print(*ans)