We want, for each tree position $$$i$$$, the maximum height that the rabbit can reach if it starts at tree $$$i$$$.

The key observation is that the rabbit’s jumping rules naturally group indices into connected components:

• If $$$i$$$ can jump to $$$j$$$, then $$$i$$$ and $$$j$$$ must be in the same component.
• Within a component, the rabbit can eventually reach the maximum height of that component.

Thus, the task reduces to: 1. Group indices into components. 2. Assign to each index the maximum height of its component.

We achieve this with Disjoint Set Union (DSU) and a monotonic stack.

Step 1. Why DSU?

• Each index belongs to exactly one connected component.
• If $$$i$$$ and $$$j$$$ are connected via the jumping rules, we merge them into the same component.
• DSU (Union-Find) is perfect for maintaining and merging such groups dynamically.

At the end, every component will have its maximum height, and each index will map to that value.

Step 2. Using a Monotonic Stack

We process the array from left to right, keeping a monotonic increasing stack (heights stored in increasing order).

At index $$$i$$$ with value $$$a[i]$$$:

• While the top of the stack has value greater than $$$a[i]$$$:
  • Pop the stack element $$$j$$$.
  • Merge $$$j$$$ and $$$i$$$ with DSU, since the forward jump rule is satisfied:

• During this popping, we keep track of the index $$$x$$$ with the maximum value inside the group.
• After processing, we push $$$x$$$ back onto the stack, ensuring the stack always represents the current group’s maximum.

This way, the stack efficiently determines which indices should be united.

Step 3. Building Components

As we iterate:

• Every time we pop from the stack, we union the popped index with the current index.
• After merging, the stack top always points to the representative index holding the largest value in the current component.

By the end of the pass:

• All reachable indices are united into components.
• Each component is correctly represented in DSU.

Step 4. Computing Maximum Heights

After building the DSU:

1. For each root in the DSU, compute the maximum $$$a[i]$$$ in that component.
2. For each index $$$i$$$, set:

Complexity Analysis

• Time Complexity:

  • Each index is pushed/popped from the stack at most once → $$$O(n)$$$.
  • Each DSU find/union is $$$O(\alpha(n))$$$ (inverse Ackermann function, practically constant).
  • Total: $$$O(n)$$$.

• Space Complexity:

  • DSU arrays + stack + result array → $$$O(n)$$$.

Intuition Recap

• The monotonic stack enforces the rabbit’s forward-jump condition (smaller height to the right).
• The DSU groups indices into connected components as jumps are discovered.
• The maximum of each component gives the rabbit’s maximum reachable height.
• Finally, each index outputs the maximum of its component.

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

def solve(arr):
    n = len(arr)

    union_find = UnionFind(n)

    stack = []

    for index in range(n):
        last = stack[-1] if stack else index
        while stack and arr[stack[-1]] > arr[index]:
            union_find.union(stack.pop(), index)
        if arr[last] > arr[index]:
            stack.append(last)
        else:
            stack.append(index)
            
    stack = []
  
    for index in range(n -1, -1, -1):
        last = stack[-1] if stack else index
        while stack and arr[stack[-1]] < arr[index]:
            union_find.union(stack.pop(), index)
        if arr[last] < arr[index]:
            stack.append(last)
        else:
            stack.append(index)
    #  For Every Componet Representative make the max value as there value
    INF = 10**18
    comp_max = [-INF for _ in range(n)]
    for node in range(n):
        root = union_find.find(node)
        comp_max[root] = max(arr[node], comp_max[root])
    ans = [ 0 for _ in range(n)]
    for node in range(n):
        root = union_find.find(node)
        ans[node] = comp_max[root]
    return ans

test  = int(input())


for _ in range(test):
    n = int(input())
    
    arr = list(map(int, input().split()))
    
    ans = solve(arr)
    print(*ans)

        

For each starting index $$$i$$$ $$$(0 \leq i \lt n)$$$, determine the maximum tree height that the rabbit can eventually reach if it begins its sequence of jumps at tree $$$a[i]$$$.

What does "maximum reachable height" mean?

• The rabbit can jump backward only to a taller tree:

• The rabbit can jump forward only to a shorter tree:

• Thus, starting at $$$a[i]$$$, the rabbit may follow a chain of jumps:

and among all reachable positions, we want the tallest tree:

This is not a purely local property. jumps may allow the rabbit to step down on the right and then reach much taller trees on the left, so we need a global way to propagate reachability.

Step 1. Build Prefix Maximums

We compute:

• $$$\text{pref}[i]$$$ stores the tallest tree up to index $$$i$$$.
• Intuition: if the rabbit is at $$$i$$$, it may eventually reach some taller tree on the left. $$$\text{pref}[i]$$$ records that possibility.

Step 2. Build Suffix Minimums

We compute:

• $$$\text{suff}[i]$$$ stores the shortest tree from $$$i$$$ to the end.
• Intuition: since the rabbit can only jump forward to smaller trees, $$$\text{suff}[i]$$$ tells us how far it can step down on the right side.

Step 3. Propagation of Reachability

Now we compute the final answer array $$$\text{ans}$$$.

1. Start at the last index:

• $$$\text{ans}[n-1] = \text{pref}[n-1]$$$(At the very end, the maximum reachable is just the tallest tree so far.)

1. Move backward from $$$i = n-2$$$ down to $$$0$$$:

• Case 1: If $$$\text{pref}[i] \gt \text{suff}[i+1]$$$

  • There is a taller tree on the left of $$$i$$$.
  • There is a smaller tree to the right of $$$i$$$.
  • This means the rabbit at $$$i$$$ can chain through the right side and eventually reach the same maximum as starting at $$$i+1$$$.
  • So we set: $$$\text{ans}[i] = \text{ans}[i+1]$$$

• Case 2: Otherwise, the chain does not extend through the right side.
  The best reachable height is just the tallest seen up to $$$i$$$:

Step 4. Final Result

• After finishing the backward pass, every index $$$i$$$ has been assigned the maximum tree height the rabbit can reach starting at $$$a[i]$$$.

• This works because:

  • $$$\text{pref}[i]$$$ ensures backward jumps are respected,
  • $$$\text{suff}[i]$$$ ensures forward “step-downs” are considered,
  • and the backward propagation of $$$\text{ans}$$$ connects reachable chains together.

Complexity Analysis

• Time:

  • Prefix array: $$$O(n)$$$
  • Suffix array: $$$O(n)$$$
  • Backward pass: $$$O(n)$$$
  • Total: $$$O(n)$$$ per test case

• Space:

  • Arrays $$$\text{pref}$$$, $$$\text{suff}$$$, $$$\text{ans}$$$ → $$$O(n)$$$

Intuition Recap

• $$$\text{pref}[i] =$$$ tallest tree so far (handles backward jumps)
• $$$\text{suff}[i] =$$$ smallest tree to the right (handles forward jumps)
• If $$$\text{pref}[i] \gt \text{suff}[i+1]$$$, then $$$i$$$ connects into the same chain as $$$i+1$$$.
• Otherwise, the maximum reachable is just $$$\text{pref}[i]$$$.

def solve(arr):

    n = len(arr)

    pref_max = [0 for _ in range(n)]
    suff_min = [0 for _ in range(n)]

    
    pref_max[0] = arr[0]

    for index in range(1, n):
        pref_max[index] = max(arr[index], pref_max[index - 1])
    suff_min[ n -  1] = arr[n - 1]
    for index in range(n - 2, -1, -1):
        suff_min[index] = min(arr[index], suff_min[index + 1])
    ans = [0 for _ in range(n)]
    ans[-1] = pref_max[-1]
    for index in range(n - 2, -1, -1):
        if pref_max[index] > suff_min[index + 1]:
            ans[index] = ans[index + 1]
        else:
            ans[index] = pref_max[index]
    return ans
            
test = int(input())
for _ in range(test):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = solve(arr)
    print(*ans)