Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

There are n parrots standing in a circle. Each parrot has a certain level of respect…

  1. User

    There are n parrots standing in a circle. Each parrot has a certain level of respect among other parrots, namely r_i. When a parrot with respect level x starts chattering, x neighbours to the right and to the left of it start repeating the same words in 1 second. Their neighbours then start repeating as well, and so on, until all the birds begin to chatter.

    You are given the respect levels of all parrots. For each parrot answer a question: if this certain parrot starts chattering, how many seconds will pass until all other birds will start repeating it? Input

    In the first line of input there is a single integer n, the number of parrots (1 ≤ n ≤ 10^5).

    In the next line of input there are n integers r_1, ..., r_n, the respect levels of parrots in order they stand in the circle (1 ≤ r_i ≤ n).

    Output

    Print n integers. i-th of them should equal the number of seconds that is needed for all parrots to start chattering if the i-th parrot is the first to start.

    Examples

    Input

    4 1 1 4 1

    Output

    2 2 1 2

    Input

    8 1 2 2 1 5 1 3 1

    Output

    3 3 2 2 1 2 2 3

  2. DeepSeek Assistant

    We need to solve: There are n parrots in a circle (positions 0..n-1). Each parrot i has a spread range r_i (an integer). When a parrot i becomes "active" (starts chattering), after 1 second, all parrots within distance ≤ r_i (to left and right) from i become active (i.e., at time 1, those neighbors become active). Then each newly active parrot j at time t becomes active and after 1 second, it spreads to its neighbors within distance r_j, and so on. This is like a BFS on a graph where each node i has directed edges to nodes within distance r_i (both directions), but the activation is simultaneous, and the time to propagate is the shortest path length (in terms of steps) from the source to all nodes in this directed graph? However careful: When a parrot becomes active, it takes 1 second to affect its neighbors. So the time for a node v to become active is the length (number of edges) of the shortest path from source s to v in the directed graph where from node i we have directed edges to all j such that distance on circle (min(|i-j|, n - |i-j|)? Actually they are arranged in a circle, and "neighbors" are immediate contiguous positions? Wait description: "x neighbours to the right and to the left of it start repeating the same words in 1 second." That means if a parrot has respect level x, then after 1 second, the x neighbors to the left and x neighbors to the right become active. But then those neighbors, when they become active, will also activate their neighbors according to their own respect levels. So each parrot i can "spread" to the set of positions within distance r_i on the circle? Actually careful: "x neighbours to the right and to the left of it start repeating the same words in 1 second." So if parrot i is active at time t, then at time t+1, all parrots that are within distance ≤ r_i in terms of index difference (on the circle, but with wraparound) become active. But is it exactly distance r_i? For example, if r_i=4, then the 4 parrots to the right and 4 to the left (i.e., up to 4 steps away) become active. So the set is all positions j such that the clockwise distance from i to j (mod n) is between 1 and r_i inclusive, and also counterclockwise distance between 1 and r_i inclusive. That is, all j with min(|i-j|, n - |i-j|) ≤ r_i? Wait but "x neighbours to the right and to the left" might be interpreted as exactly the x immediate neighbors on each side? In a line it's clear: the parrot at index i can directly activate i-1, i-2, ..., i-r_i and i+1, i+2, ..., i+r_i, provided they exist (wrap around because it's a circle). So yes, it's a range of length r_i on each side. So it's like each node has a directed reach of intervals of length r_i in both directions, but not necessarily all nodes within a distance less than r_i? Actually it's exactly the set of nodes whose circular distance (i.e., minimal steps along the circle) is ≤ r_i? Wait if we consider neighbors as contiguous chain of length r_i on each side, then total count is 2r_i (unless r_i > floor((n-1)/2) for some? But the statement: "x neighbours to the right and to the left of it start repeating the same words in 1 second." It doesn't say that the neighbors are contiguous or that the activation is simultaneous to all those within distance x. Typically, "x neighbours to the right and to the left" suggests the first x neighbors on each side, i.e., the nodes at distances 1,2,...,x along the circle in each direction. That is indeed the set of nodes whose distance along the circle (in either direction) is ≤ x? But careful: Suppose x=2. Then to the right: the parrot at i+1 and i+2 become active. To the left: i-1 and i-2. So all nodes with absolute index difference ≤2 become active? But due to circle, we consider wrap-around. So yes, all nodes with circular distance ≤2 become active. But if n is small, say n=4, x=4? Actually r_i ≤ n, but they can be up to n. So if x >= n/2, then the two sides may overlap? In a circle, the set of neighbors to the right of length x and to the left of length x may double-cover many nodes. But the activation is immediate: all those nodes become active after 1 second. So effectively, node i can directly activate any node j such that the minimal number of steps along the circle from i to j is ≤ r_i? Because the right side includes nodes at distance 1..r_i clockwise, left side includes 1..r_i counterclockwise. But the node at distance exactly 2 clockwise is also reachable as part of the right side. But what about a node at distance 2 clockwise? Yes. So the direct activation set is exactly the ball of radius r_i in the circular graph where each edge connects adjacent parrots? Actually the circle's adjacency is between neighbors (distance 1). But here the activation jumps over multiple nodes at once. So the direct activation range is a "jump" of up to r_i steps.

    Thus we can model as a directed graph where from i we have edges to all j such that the circular distance from i to j is ≤ r_i (excluding i itself). That is, we have edges to a contiguous interval on the circle in both directions. But note: Because the graph is directed, the edges from i to j are defined by r_i, not symmetric.

    Goal: For each source s, find the minimal time (in seconds) such that all nodes become active. Since each step takes 1 second, and activation propagates in parallel, the time is the length of the longest shortest path from s to any node in this directed graph (i.e., the directed graph's eccentricity of s). However, we need to be careful about the simultaneous spreading: When a node becomes active at time t, it starts to affect its neighbors, which become active at time t+1 (if not already active). This is exactly BFS propagation. So yes, time for full activation = the number of steps (distance) in the BFS tree (the maximum distance from s). So we need the eccentricity of s in the directed graph.

    But n up to 1e5, we cannot do BFS from each node. So need to precompute something or use a more efficient method.

    We have a circle, so positions are modulo n. Each node i has a radius r_i (integer between 1 and n). The directed edges: i -> j if the clockwise distance from i to j (or counter?) is ≤ r_i? Actually it's symmetric: "x neighbours to the right and to the left" means both directions independently. So j is reachable in one step from i if either (j - i) mod n ∈ [1, r_i] or (i - j) mod n ∈ [1, r_i]. Equivalently, if the circular distance (minimal number of steps along circle) ≤ r_i? But careful: Suppose r_i=3, n=10. The node at distance 9 clockwise has minimal distance 1? Actually on a circle, distance can be measured as the shortest path in terms of steps along adjacency: the minimal number of steps moving to neighbor each step. That is min(clockwise distance, counterclockwise distance). The node at clockwise distance 9 is at counterclockwise distance 1, so minimal distance = 1. So it would be included if r_i>=1, which it is. So yes, the condition is that the minimal distance ≤ r_i. But does that capture the asymmetry? The node at distance 9 clockwise is reachable because it is only 1 step counterclockwise? But wait, the parrot can activate neighbors to the left and to the right up to r_i. That means it can directly activate nodes that are within r_i steps along the circle in either direction, regardless of the minimal distance. So consider a node at clockwise distance 9 when n=10, r_i=3. Clockwise distance is 9 (>3), counterclockwise distance is 1 (≤3). So it should be reachable because it is a neighbor to the left? But if we consider "to the left", it's the immediate neighbor in the counterclockwise direction, but the parrot can activate up to r_i neighbors on the left, meaning nodes at distances 1..r_i counterclockwise. So yes, the node at counterclockwise distance 1 is included. So it's reachable. So condition is: j is reachable if either the clockwise distance d_cw(i,j) ≤ r_i or the counterclockwise distance d_ccw(i,j) ≤ r_i. Since d_cw(i,j) + d_ccw(i,j) = n (or n? Actually for i≠j, d_cw(i,j) + d_ccw(i,j) = n because if you go clockwise all the way around you get n, but that's including the zero? Let's define: positions 0..n-1. The clockwise distance from i to j is (j - i) mod n (value in [0, n-1]). But if j = i, distance 0. For j≠i, clockwise distance is (j - i) mod n ∈ [1, n-1]. The counterclockwise distance from i to j is (i - j) mod n ∈ [1, n-1]. And indeed, clockwise + counterclockwise = n. So if one is ≤ r_i, the other is ≥ n - r_i. So the condition is min(d_cw, d_ccw) ≤ r_i, because if the clockwise distance is > r_i, but counterclockwise ≤ r_i, then min ≤ r_i. So it's equivalent to the condition that the minimal distance on the circle (i.e., graph distance in the undirected cycle) is ≤ r_i. So the direct activation set is the ball of radius r_i in the undirected cycle graph. Interesting. Because the undirected cycle distance between i and j is min(|i-j|, n - |i-j|). That is exactly ≤ r_i.

    Thus from i we can activate all nodes within undirected distance ≤ r_i in one second. So the directed graph is actually symmetric in terms of distances, but the radii may differ per node. So it's like each node has a "range" r_i, and propagation can jump to any node within that range in one step.

    Now we need the eccentricity: the smallest number of steps needed to reach all nodes from s, where each step from a node u can go to any node within distance r_u from u.

    This is a classic problem: given points on a circle with each having a "jump radius", we want the minimal number of jumps to cover all nodes starting from a given node. It's akin to the broadcast time in a graph where each node can cover an interval around itself. The problem can be transformed into a problem on a line or circle by considering coverage intervals.

    Because the graph is undirected? Wait edges are directed from u to v if distance(u,v) ≤ r_u. However, propagation is directed, but we can think of the process as spreading; after a node becomes active, it can activate others according to its own radius. So it's a directed process. However, the graph might be strongly connected? Possibly if r_i are large enough. But we need the shortest path distances in this directed graph.

    Alternatively, we can consider that the process essentially expands the set of active nodes over time: initially only s active. At each step, for every active node u, we add all nodes within distance r_u. This is like a BFS in a directed graph with certain jumps.

    We need to compute for all sources. That's challenging.

    Let's try to think of this as a kind of "range expansion" problem that can be solved using DP or monotonic queues, similar to the problem of computing the number of steps to cover a line with given coverage radii, but on a circle.

    One approach: For each source s, the process resembles the following: We have intervals that expand. At time 0, we cover just s. At each step, we consider all currently covered points, and for each such point i, we cover the interval [i - r_i, i + r_i] (mod n) on the circle. But because the circle is symmetric, we can "unroll" it by considering positions modulo n.

    But the process is not simply taking the union of intervals and then expanding further; the new points themselves have different radii, so they may extend coverage further.

    Goal: The time until all n nodes are covered.

    This is reminiscent of the "minimum broadcast time" problem on a graph which is NP-hard in general, but here the graph has special structure: it's a directed graph based on intervals on a circle.

    Perhaps we can reframe it as: Starting from s, we want to find the minimum T such that there exists a sequence of activations that covers all nodes within T steps, but we have the freedom to choose which order to activate? But BFS gives the optimal because all edges have unit weight and propagation happens in parallel. So the time is the length of the shortest directed path from s to each node, and the maximum over nodes is the answer.

    So we need to compute, for each node s, the maximum over t of the shortest path distance from s to t.

    Given the graph is directed, we can't easily invert.

    Maybe we can consider that the process can be thought as: at time 0, the "frontier" is {s}. At time step k, we have some active set A_k. Then A_{k+1} = A_k ∪ (∪_{i∈A_k} B(i, r_i)), where B(i, r) is the ball of radius r around i (undirected). This is like a coverage expansion.

    Alternatively, we can think of the distances as the minimal number of hops needed to reach a node, where each hop from node u can move at most r_u steps in either direction along the circle.

    This is similar to problems like "jump game" but with varying step lengths, and we need the number of jumps to cover all positions. But here it's on a circle, and we need for each start.

    Maybe we can convert to a problem on a line by breaking the circle at some point. But because the graph is symmetric on the circle, the answer for each node might be computed via some DP that processes intervals.

    Another thought: Since r_i ≤ n, we might think of constructing a graph where each node has edges to "next" and "previous" with some lengths? Not exactly.

    Let's try to solve for a line first (n nodes in a line, no wrap). For each start position, find the time to cover all nodes. That might be easier, and then extend to circle by duplication.

    Consider positions 1..n on a line. Each node i has a radius r_i (could be up to n). When active, it can activate nodes in [i - r_i, i + r_i] ∩ [1, n]. Starting from s, we spread. Want the minimal number of steps to cover all.

    This is reminiscent of the "virus spread" problem or "broadcast time" on a line with varying ranges. Might be solved by greedy: At each step, the active set is an interval (or union of intervals) but due to varying radii, it might be multiple intervals? Actually, on a line, because activation starts from a single source and spreads outward, it's plausible that the active set remains a contiguous interval? Let's test: Starting from s, initially {s}. Then after first step, we add all nodes within [s - r_s, s + r_s]. This is an interval. Now suppose we have active interval [L,R] (contiguous). At next step, any node i in [L,R] can activate nodes in [i - r_i, i + r_i]. The union of these intervals is likely to be an interval as well, because if we have leftmost active node L and rightmost active node R, the leftmost possible newly covered node is min_{i in [L,R]} (i - r_i), and rightmost is max_{i in [L,R]} (i + r_i). So the new active set becomes [min(L, min_{i} (i - r_i)), max(R, max_{i} (i + r_i))] intersected with [1,n]. Since min_{i in [L,R]} (i - r_i) could be less than L, and similarly for max. So the active set remains a contiguous interval. This is because the activation is symmetric and we start from a contiguous interval. So indeed, on a line, the active set is always a contiguous interval [L,R] containing s. This simplifies: The process becomes: we start with L=R=s. At each time step, we update L <- min(L, min_{i in [L,R]} (i - r_i)) and R <- max(R, max_{i in [L,R]} (i + r_i)). This is like expanding the interval based on the "potential" of points inside.

    Thus, the number of steps until [L,R] covers [1,n] is the minimal t such that after t expansions, the interval covers all.

    This is similar to a problem of "covering a line with ranges" where each point has a left extension (i - r_i) and right extension (i + r_i). Starting from a seed, we iteratively expand the interval by taking the min left extension among points in the current interval, and similarly for right.

    We can think of it as: Define L_i = i - r_i, R_i = i + r_i. The process is: we have current interval [l,r]. Then next interval = [min_{i in [l,r]} L_i, max_{i in [l,r]} R_i].

    This is reminiscent of the "jump intervals" method: We want to compute the number of steps needed to reach full coverage.

    We can precompute something like the "reach" after multiple steps. This is analogous to building a segment tree or using a doubling technique (binary lifting) to compute after 2^k steps what the expanded interval becomes. Because the expansion depends only on the current interval, not on the history? Actually, the expansion from interval I = [l,r] is deterministic: we compute new bounds as min L_i for i ∈ I and max R_i for i ∈ I. But careful: The interval I always contains all points that have been activated. Since the activation process is monotonic and we always expand to cover more, the set remains the interval. So we can define a function f that maps an interval [l,r] to a new interval [l', r'] where l' = min_{i ∈ [l,r]} L_i, r' = max_{i ∈ [l,r]} R_i. However, note that the interval may also include points that were not originally in [l,r] but after expansion we add them. But then for the next step, we need to consider the L_i, R_i of those newly added points as well. So the function applied to interval [l,r] should incorporate the new points: it's not just using the old interval's points to compute min and max, but we actually update the interval to the union of [l,r] and the coverage from points in it. So the resulting interval is the union of [l,r] with the coverage from points in it. That's exactly [ min(l, min_{i∈[l,r]} L_i), max(r, max_{i∈[l,r]} R_i) ].

    So define F([l,r]) = [ min(l, min_{i∈[l,r]} L_i), max(r, max_{i∈[l,r]} R_i) ].

    Because we start with [s,s], we repeatedly apply F until we get [1,n].

    Now, for each starting s, we need the number of iterations until we reach full coverage. This is similar to computing the "closure" or "fixpoint".

    We can preprocess data to answer queries: given starting point s, how many steps to cover the line? And we need to do this for all s efficiently.

    Now, on a circle, the active set might not remain a single interval because the circle is cyclic. But we can break the circle at some point and consider the line, but we need to handle wrap-around. However, because the graph is symmetric on a circle, the active set might become an arc (contiguous segment on the circle) and eventually the whole circle. Starting from a single node, the activation should spread around in both directions, and because it's a circle, the active set will be a contiguous arc (maybe wrapping around) until it covers the whole circle. At the point when the arc length becomes n, it's full.

    But note: On a circle, if we start with a point, the active set will be a contiguous arc (i.e., a set of consecutive positions modulo n) because the activation spreads outward in both directions without gaps. This holds for the same reason as on a line: at each step, the union of intervals from points in the current arc will produce a (possibly larger) arc (maybe covering more than half the circle, but still contiguous). However, careful: On a circle, an arc could be defined as a set of consecutive positions modulo n. Starting from s, after first step, we get the arc from s - r_s (mod n) to s + r_s (mod n) going through s (i.e., the set of positions within distance r_s along the circle). That's a contiguous arc of length 2r_s+1 (if r_s < n/2) or the whole circle if r_s >= n/2. If r_s >= n/2, then it covers the whole circle immediately (since the ball of radius >= n/2 covers all nodes because the maximal distance between two points on a circle is floor(n/2) for minimal distance? Actually minimal distance max is floor(n/2). If r_i >= floor(n/2), then the ball of radius r_i covers all nodes because for any j, the minimal distance <= floor(n/2) <= r_i. So yes, if r_i >= ceil(n/2)? Actually, minimal distance between any two distinct points is at most floor(n/2). If n is even, the farthest points have distance n/2. So if r_i >= n/2, then it covers all. For odd n, max distance is floor(n/2). So condition r_i >= ceil(n/2)? For n=5, floor(5/2)=2. If r_i=2, ball radius 2 covers all? Distances: 0,1,2. The farthest distance is 2, so yes. So if r_i >= floor(n/2), then ball covers all. Actually for n odd, floor(n/2) = (n-1)/2, which is the maximum minimal distance. So if r_i >= (n-1)/2, it covers all. For even n, maximum distance is n/2. So if r_i >= n/2, covers all. So condition is r_i >= ceil(n/2)? For odd n, ceil(n/2) = (n+1)/2 > floor(n/2). But we need r_i >= floor(n/2). So it's not exactly ceil. So careful: The maximal minimal distance is floor(n/2). So if r_i >= floor(n/2), then ball covers all. That condition is r_i >= floor(n/2). For even n, floor(n/2)=n/2, so r_i >= n/2; for odd n, floor(n/2)=(n-1)/2, so r_i >= (n-1)/2. So yes. Since r_i can be up to n, many could cover all immediately. In that case answer for that source is 1 (if r_i >= floor(n/2)? Actually if s covers all in one step, answer = 1? Wait: starting from s at time 0, after 1 second all other birds become active. So answer = 1. If r_s = n (covers all), then yes. But even if r_s is enough to cover all directly, answer is 1. But we must consider that the source itself is already active at time 0, but others become active at time 1. So time is 1.

    If not immediate, we need multiple steps.

    Now, because the active set remains a contiguous arc (maybe wrapping), we can map the circle to a line by cutting at some point. But the choice of cut might depend on the source. A typical technique: duplicate the array to handle circular intervals. For each possible starting point s, we can consider the line from s to s+n-1 (positions modulo n). Then the active set will be an interval on this line that contains s, and we want to know how many expansions to cover the whole length n. However, the radii are defined on the circle, so when we duplicate, the L_i and R_i values for positions beyond n need to be adjusted appropriately: For a position i (0-indexed), its L_i = i - r_i, R_i = i + r_i. On the circle, these are modulo n, but when we unroll to a line, we need to treat the indices modulo n, but the activation is based on the actual circle distances: the ball of radius r_i around i on the circle corresponds to an interval [i - r_i, i + r_i] modulo n, which on the unrolled line (with duplication) might be represented as two intervals if it wraps. However, if we always keep our consideration within a line segment that is long enough (say length 2n) and we ensure we never need to consider wrap-around because we start from s and the active arc expands outward and eventually might wrap around the circle, but in the line representation, covering the whole circle corresponds to covering an interval of length n starting at s. That is, we want to expand from s to cover [s, s+n-1] on the line (with indices modulo n). The active set on the line might be an interval [left, right] that always stays within some range? Actually, because the activation on the circle can go both ways, on the unrolled line, starting from s (position s in the duplicated array), the active set might be an interval that expands leftwards and rightwards. But the circle condition means that if we cross the boundary of the original [0, n-1] we may need to consider indices beyond that. However, if we duplicate the array twice (or three times) we can simulate.

    A standard trick: For problems on a circle with intervals, we duplicate the array of length n to length 2n (or 3n) to handle wrap-around. Then we consider the starting point at position s in the original, and also at s+n (the duplicate). Then we want to know the minimal steps to cover a segment of length n (i.e., from s to s+n). Because the circle is covered when the active interval covers all positions from s to s+n (since s and s+n are the same point on the circle, covering the whole circle corresponds to covering an interval of length n in the duplicated line that starts at s and ends at s+n). However, we have to be careful: The activation rules are based on the original circle distances, not on the linear distance on duplicated line. But if we duplicate the array with the same values (r_i repeated), then for a point at index i (0 ≤ i < n), its duplicate at i+n has the same r_i. The distance on the circle between i and j is min(|i-j|, n - |i-j|). On the duplicated line, if we consider indices i and j (with i possibly in [0,2n-1]), the minimal circular distance can be computed as min(|i-j|, n - |i-j|) but also considering that if |i-j| > n, it's not minimal. Typically, to avoid wrap, we restrict our attention to intervals of length at most n. For any two points on the circle, we can represent them as positions on the line such that their distance is the circular distance if we take appropriate representation. When we duplicate, if we consider an interval of length less than n, the circular distance between two points within that interval equals their linear distance if the interval length ≤ n and we take the appropriate orientation. More specifically, if we fix a starting point s and consider the line from s to s+n, then for any two points i and j in that segment, the circular distance between them is min(|i-j|, n - |i-j|). Since |i-j| ≤ n (because the segment length is n), it's possible that |i-j| could be > n/2, then the circular distance would be n - |i-j|, which is less than |i-j|. That means the linear distance may overestimate. But our activation condition is based on circular distance: i can activate j if circular distance ≤ r_i. On the line segment from s to s+n, if we consider the linear distance, we might erroneously think that two points far apart in linear sense but close circularly (i.e., across the boundary) are not close. However, because we have duplicated the array, the point j may also appear at j-n or j+n. To capture the circular distance accurately, we need to consider the representation that yields the minimal distance.

    In many problems, if we duplicate the array and then consider intervals, we can treat the activation as: from i, it can reach all j such that |i - j| ≤ r_i, but also due to wrap, it can reach j+n? Actually, if we have duplicated positions, we could define that each node i (in original) has copies at i and i+n (and maybe i+2n). Then the ball of radius r_i around i (in terms of circular distance) is equivalent to the set of indices j in [i - r_i, i + r_i] (in linear sense) but also the set of indices j+n in that interval? Let's think.

    Better: We can transform the circle problem into a line problem by cutting the circle at a point that is not initially active, but we don't know it. Instead, we can treat the activation as covering an arc. At any point, the active set is an arc. Let's define positions 0..n-1 on a circle. The active arc is described by its leftmost and rightmost boundaries in terms of some orientation. However, because it's an arc, we can represent it by an interval [L, R] modulo n (with length maybe up to n). But it's simpler to fix a reference point and treat the circle as a line by "unfolding" at the starting point s. That is, we consider the line of positions s, s+1, ..., s+n-1 (mod n). For each position x on this line, its actual index mod n is x mod n. The circular distance between two positions a and b (mod n) is min(|a-b|, n - |a-b|). If we restrict a and b to be within a contiguous interval of length at most n, the minimal circular distance might be either |a-b| or n - |a-b|. For a contiguous interval of length n, the two endpoints are distance n apart, which corresponds to the same point on the circle; their circular distance is 0. But for interior points, if the interval is exactly n, then for points near opposite ends, the linear distance might be > n/2, while the circular distance is n - linear distance, which is smaller.

    Thus, the direct activation condition based on linear distance on this unrolled line is not equivalent to circular distance. However, we can use the property that the active set is an arc, and we can always represent it as an interval that does not wrap around, as long as we choose the representation appropriately. Initially, the active set is a single point, we can consider the circle cut at that point? Actually, we can define the arc as starting from the leftmost active point (in clockwise order) to the rightmost active point (in clockwise order) without crossing some reference. Since it's an arc, there is a representation where the active set is a contiguous block of indices modulo n, but you can always rotate indices so that the active set is an interval that doesn't wrap. For a given source s, we can rotate the indexing so that s is at position 0, and consider indices 0..n-1 with wrap at n. Then the active set will be an interval [L,R] where L ≤ 0 ≤ R initially? Actually, starting at 0, after first expansion, it becomes [-r_s, r_s] modulo n, which wraps if r_s > 0? But we can handle by using an array duplicated twice and considering positions from 0 to 2n-1, with start at n (or at position n to avoid negative). For convenience, shift indices so that the source s is at position 0 (or at n) and then we consider the line from 0 to n (or 0 to n-1). However, the activation might go negative; we can add offset.

    A common technique: duplicate the array three times (or at least two times) and then consider the process on the line where the distances are measured linearly, but we also adjust the radii to be effective on that line? Actually, maybe we can convert the circular problem to a line problem by "breaking" the circle at the point opposite to the source? Let's think differently.

    Alternative approach: Since the active set is always an arc containing the source, we can think of the spread as expanding left and right from the source along the circle. Because it's a circle, we can think in terms of two frontiers: one moving clockwise from s, and one moving counterclockwise from s. However, due to varying radii, the expansion of each frontier may be aided by points that are already covered in between. This is similar to a process where we have leftmost and rightmost covered positions, and we extend them based on the "coverage" of points within the covered interval.

    Specifically, define positions on the circle. Let's fix an orientation: clockwise direction. Represent positions as numbers modulo n. Starting from s, let the covered arc be from L to R (clockwise from L to R passing through s). Initially L = R = s. At each step, we can compute new L' as the minimum over i in the arc of (i - r_i) (mod n) but careful with mod: subtracting r_i in the clockwise direction? Actually, "neighbours to the left" likely means counterclockwise? But we need a consistent orientation. Let's define positions on a circle with indices 0..n-1 in clockwise order. Then "left" might be ambiguous. But we can define that each parrot can activate all parrots within distance r_i in either direction along the circle. So from i, the reachable set is all j such that the circular distance ≤ r_i. This is symmetric.

    If we think in terms of arcs, we can define two frontiers: the leftmost (counterclockwise extreme) and rightmost (clockwise extreme). Because the activation can go both ways, the arc expands outward.

    But the circle introduces the possibility that the arc might eventually wrap, i.e., L may be greater than R if it passes through 0. But we can handle that by always normalizing.

    Maybe we can instead consider the problem as the "minimum number of jumps to cover a circle" where each point i can jump up to r_i distance (in terms of index difference). But the jumps are directed: from i, you can go to any point within distance r_i. Starting from s, we want the minimum number of steps to reach all points. This is essentially the graph distance in a directed graph. However, because the graph is highly structured, perhaps we can compute distances using BFS with some optimizations like segment tree or monotonic queue? But we need all sources.

    Let's try to think about a known problem: "If you have an array and each index i can jump to any index in [i - a_i, i + a_i], what is the minimum number of jumps to cover the whole array from a given start?" That's like the minimum number of rounds to cover all indices. This is similar to the "frog jumping" but covering all points. There's known concept of "coverage spreading" that can be solved with greedy and segment trees. For a fixed start, we can compute the number of steps by repeatedly expanding interval, which can be done in O(log n) per step, but steps may be up to O(n) in worst case? However, maybe we can precompute the "reach" after many steps using binary lifting.

    Define for an interval [l, r] (on a line, 1-indexed), the function F(l, r) = [min_{i∈[l,r]} L_i, max_{i∈[l,r]} R_i] where L_i = i - r_i, R_i = i + r_i. But note that L_i can be less than 1 and R_i can be greater than n. To cover the whole line [1,n], we need to reach L ≤ 1 and R ≥ n.

    Now, for a given start s, we iterate: interval = [s,s]; step = 0; while interval not covering [1,n], interval = F(interval); step++. The number of steps is the answer.

    Now, how to compute step count quickly for all s? Possibly we can precompute for each position the "power" of expansion after k steps. Since F is monotonic and deterministic, we might compute the closure in O(log n) steps using binary lifting on intervals.

    Specifically, we can define a "jump" function that, given an interval [l,r], after 2^k steps, we can compute the resulting interval. That is, we can precompute arrays f_k(l, r) that give the interval after 2^k steps. But the state space of intervals is O(n^2) which is too large.

    But we can notice that the interval after any number of steps starting from a point s will always be of the form [L(s,t), R(s,t)] where L and R are some functions. Maybe we can treat left and right expansions separately? Actually, the expansion is symmetric? Not exactly, because L_i and R_i are independent. However, the process is similar to: left bound expands leftwards based on the minimal L_i among covered indices, and right bound expands rightwards based on maximal R_i.

    We might compute for each possible left bound and right bound, but that seems complex.

    Alternative: The process from a single source is analogous to repeatedly taking the "minimum L" and "maximum R" over the current interval. This can be thought as: we start with L0 = R0 = s. Then L1 = min_{i in [s,s]} L_i = s - r_s; R1 = s + r_s. Then L2 = min_{i in [L1,R1]} L_i; R2 = max_{i in [L1,R1]} R_i, etc.

    So essentially, we need to compute the closure under taking mins of L and maxes of R over intervals.

    This is reminiscent of the "interval expansion" problem that can be solved using a segment tree or sparse table to quickly find the min L and max R over a range, and then iteratively expand. Since each expansion potentially increases the interval, and the number of expansions until full coverage might be O(n) in worst case? But maybe we can accelerate using binary lifting: we can precompute for each index i, after 2^k steps, what interval we would have if we start from i? However, the interval after 2^k steps is not determined solely by the starting point? Actually, if we start from a single point s, after 1 step we have [L1,R1] which is [s - r_s, s + r_s]. After 2 steps, we have [L2,R2] = [min_{i in [L1,R1]} L_i, max_{i in [L1,R1]} R_i]. So the state is the interval. So if we want to apply binary lifting, we need to represent the transformation from interval to interval. But note that the transformation F is monotonic and idempotent? Not idempotent. But we can precompute data structures to compute F(interval) quickly, and then simulate the process in O(log n) steps by using a technique similar to "jumping to next expansion where min L or max R changes"? Actually, we can perhaps compute the number of steps using a BFS-like approach similar to "minimum number of intervals to cover whole line", which can be solved by greedily picking the farthest reachable at each step, akin to the classic "minimum number of jumps to cover array" problem. Wait, there's a known problem: Given an array a[i] (jump lengths), starting at index s, you want to cover all indices by repeatedly jumping: at each step, from any covered index i, you can cover all indices within distance a[i]. That's exactly our process. And we ask the number of steps to cover entire array. This is similar to the "infection spread" problem. It can be solved by simulating the expansion of the covered interval: at each step, the new interval becomes the union over i in current interval of [i - a[i], i + a[i]]. This is essentially the same as the interval expansion.

    Now, is there a known O(n) algorithm to compute the number of steps for all starting positions? Possibly using DP from ends.

    Let's think differently: The answer for a given source s is the smallest t such that after t steps, the interval covers [1,n]. This is like the "distance" in a graph where nodes are intervals? Not sure.

    Observing that the expansion process is monotonic and the interval only expands outward, we can think about the leftmost uncovered point and rightmost uncovered point. But perhaps we can compute the time as the number of times we need to "expand" the interval until it covers everything. This is reminiscent of the concept of "radius" in a directed graph with interval reachability.

    Another approach: Model the problem as a graph where each node i has directed edges to i- r_i .. i+ r_i. Then the distance from s to any node t is the minimum number of hops. We need the maximum distance over t. This is the eccentricity. This graph is a directed interval graph. There is known result: The eccentricity can be computed via a "shortest path" which can be solved by BFS with segment tree (range updates) because edges go to ranges. For a single source, we can compute distances in O(n log n) using Dijkstra-like BFS with segment tree to set distances for whole intervals. But we need for all sources, which would be O(n^2) worst-case.

    But maybe we can compute the answer for all sources simultaneously using some symmetry or using the concept of "center" of the graph? Since the graph is directed and not symmetric, it's tricky.

    Another angle: The process can be seen as: In each second, all active parrots spread according to their radii. This is similar to a "broadcast" process. The time until all are active is the smallest t such that the t-fold iteration of the expansion covers all.

    Notice that the expansion only depends on the extremes of the active interval: the leftmost active point and the rightmost active point. But is that true? The new left bound is min_{i in [L,R]} L_i, which depends on all points in the interval. However, the min of L_i over the interval is simply the minimum L_i over that interval, which could be precomputed with range minimum queries. Similarly for max R_i. So we can compute F(L,R) using RMQ.

    So if we can, for any interval [L,R], quickly get newL = min(L_i for i∈[L,R]) and newR = max(R_i for i∈[L,R]), we can simulate expansion. Starting from [s,s], we iteratively update until L ≤ 1 and R ≥ n.

    The number of iterations might be O(n) in worst case? Possibly yes, because each step could expand by only one. Example: r_i = 1 for all i. Then starting from s, step1: interval becomes [s-1, s+1]; step2: becomes [s-2, s+2]; etc. So number of steps is about distance to farthest end, i.e., max(s-1, n-s). That's O(n). So for n up to 1e5, O(n) per source is too much. Need faster.

    But maybe we can compute answer for all s in O(n) total using some clever method.

    Consider the line case first. There's a known technique: For each i, define L_i = i - r_i, R_i = i + r_i. The expansion process from start s can be seen as:

    Let L0 = R0 = s. Define L_{k+1} = min_{i ∈ [L_k, R_k]} L_i R_{k+1} = max_{i ∈ [L_k, R_k]} R_i

    We stop when L_k ≤ 1 and R_k ≥ n.

    Now, note that L_k is non-increasing and R_k is non-decreasing. The sequence of intervals is monotonic.

    We could precompute the "next expansion" using a concept of "jump pointers". For each position x, define left_next[x] = min_{i ∈ [x, ?] }? Not straightforward.

    Observe that the process is similar to computing the "closure" of the interval under the "cover" function. This is reminiscent of the "farther you can reach" as in the problem of "minimum number of intervals to cover a range". Actually, think of it as: we have intervals [L_i, R_i] associated with each point i. Starting from point s, we take its interval. Then we take the union of intervals of all points in the current covered range. This expands to the convex hull (minimum L, maximum R). Then we repeat. This is like repeatedly taking the union of intervals of points within the current range.

    We could consider a graph where each point i has an edge to all points in [L_i, R_i]. Then the distance from s to t is the minimum number of hops. But maybe we can compute the eccentricity by looking at the directed graph's strongly connected components? Not helpful.

    Maybe there is a simpler characterization: The time needed for source s equals the smallest integer t such that there exists a sequence of indices s = i0, i1, ..., it where each step's radius covers the next, but also we need to cover all nodes. Actually, the time to cover all nodes is the maximum over t of distance(s, t). So we need the furthest distance.

    We can think about the "distance" from s to a point t. Since the graph is directed and edges go to intervals, the distance might be computed via a kind of "interval BFS" where we can compute distances to all nodes from s in O(n log n) using a segment tree, as previously mentioned. That's okay for a single source but not for all.

    Maybe we can reverse the graph: For each node t, consider the set of nodes that can reach t within k steps. But that's similar.

    Given constraints (n up to 1e5), we might need O(n log n) total time.

    Consider the possibility that the answers can be computed using some sort of DP that leverages monotonicity. Let's attempt to analyze the process more deeply.

    First, note that the process is symmetric if we reverse the line. So answer for s on a line might be something like max( distance to left end, distance to right end ) in terms of "effective jumps". But not exactly because jumps are variable. For constant r_i=1, it's simply max(s-1, n-s). For r_i=2, the expansion is faster.

    Maybe we can think of the process as: at each step, the leftmost active index L moves left by at most the maximum "left expansion power" among the active indices. That maximum left expansion power is the maximum (i - L_i) = r_i? Actually L_i = i - r_i, so the amount left expansion contributed by index i is r_i (since from i, you can reach i - r_i). So the left bound can be reduced by up to the maximum r_i among active indices. But the active set is an interval, so the left bound will be reduced to the minimum L_i among indices in the interval. That minimum L_i is essentially i - r_i for some i in the interval. So the new left bound = min_{i in [L,R]} (i - r_i). This can be less than L - max_{i in [L,R]} r_i? Not necessarily.

    We can define for each i, its left reach: left_i = i - r_i, and right reach: right_i = i + r_i.

    Then the process is: Starting from s, we set L = s, R = s. Then repeatedly: L <- min( L, min_{i in [L,R]} left_i ) R <- max( R, max_{i in [L,R]} right_i )

    Since L and R are monotonic, we can think of them moving outward.

    Now, imagine we precompute two functions:

    • For any interval [a,b], define leftMin(a,b) = min_{i in [a,b]} left_i.
    • rightMax(a,b) = max_{i in [a,b]} right_i.

    We need to find the number of iterations until L ≤ 1 and R ≥ n.

    This is similar to the process of taking the convex hull of the union of intervals of points in the current range.

    One way to accelerate is to use a binary lifting / doubling technique on intervals. Since the operation F is deterministic and monotonic, we can precompute, for each possible interval [L,R]? But there are O(n^2) intervals.

    But note that the state is completely determined by the pair (L,R). However, maybe we can compress the state: Because we always start from a point, and after first step the interval is [left_s, right_s]. Then after second step, it's [min_{i in [left_s, right_s]} left_i, max_{i in [left_s, right_s]} right_i]. So it's the min left and max right over the interval from previous step.

    Now, if we precompute for each index i, the "range" after one step from i is interval I_i = [left_i, right_i]. After two steps from i, we need to apply F to I_i. But note that after two steps, it's not simply I_j for some j.

    Maybe we can think in terms of "jump" pointers: For each position i, we could compute how far left we can eventually get if we start at i and expand repeatedly? But we also have right expansion.

    Could the answer for a source s be determined by some kind of "closure" of the intervals? Possibly the number of steps equals the number of times we need to take the min left and max right until we cover all. This resembles the concept of "interval graph powering".

    Another angle: This process can be simulated using a BFS-like method where we treat the leftmost and rightmost as two frontiers. At each step, we can compute the new leftmost as the minimum left_i among i in current interval. To avoid iterating over the interval, we can precompute segment tree for range min left_i and range max right_i. Then each step takes O(log n). Since the number of steps might be O(n) in worst case (like r_i=1), overall O(n^2 log n) for all s is too high. But perhaps for all s, we can compute answers in O(n log n) total using something like multi-source BFS? Or maybe we can compute all answers by analyzing the structure.

    Consider the trivial case where all r_i = 1. Then the answer for s is max(s-1, n-s) (1-indexed). That's easy. For general r_i, we need something like the "distance" in a graph with edges of length 1 to intervals.

    Maybe we can compute distances from all nodes to all others using a variant of Dijkstra with segment tree for range updates, but from all sources simultaneously? That's like computing the all-pairs shortest path distances in a graph with special structure, but we only need the eccentricity for each source. However, the graph is directed and not necessarily symmetric. Could we compute the "radius" of each node in this directed graph efficiently?

    Perhaps we can think in terms of "cover time" by modeling as a kind of "fire propagation" on a line where each point i can spread fire to a range. There is known concept: The minimal time to cover the line starting from a point is the smallest t such that the t-th iterate of the "coverage function" covers the whole line. This can be computed using a "farthest point" concept.

    Idea: The process is analogous to repeatedly taking the function f(X) = X ∪ (∪_{i∈X} [i - r_i, i + r_i]), where X is a set (initially {s}). Since the set remains an interval, we can define f on intervals. The iteration f^t([s,s]) yields an interval. The answer is smallest t with f^t covering all.

    Now, suppose we define two sequences: L_t and R_t as above. Notice that L_t is non-increasing and R_t non-decreasing. Moreover, the evolution of L_t depends on the values of left_i for i in [L_{t-1}, R_{t-1}], which is a range that expands. So we can think of L_t as the minimum left_i over an interval that is expanding. This is similar to "range minimum query with expanding range".

    One possible approach: For each possible left bound L, we could compute the rightmost index that can be reached from s in certain steps, etc.

    Given the constraints (n=1e5), we might try to compute the answer for all s using a BFS-like technique that processes nodes in order of distance. But we need distances from each node to all others? Wait, we need eccentricity, i.e., maximum distance from s. That's like the "worst-case" distance. Maybe we can compute for each node the distance to the farthest node using some symmetry? Or maybe we can compute the "distance to cover all" by looking at the leftmost and rightmost uncovered points. Because the process is monotonic, the time to cover all is the maximum of the time to cover the left side and the time to cover the right side, but they interact because expansion on one side can be helped by points from the other side. However, due to the interval property, the leftmost point becomes covered when some active point on the right can reach it. But the active set is contiguous, so covering the leftmost point essentially means that the left bound L_t reaches 1. Similarly for right bound.

    Thus, the answer is the larger of the number of steps needed to reach left end and to reach right end? Not exactly, because steps are simultaneous and the expansion on both sides can be aided by points that become active earlier. But maybe we can compute the minimal number of steps to expand from s to cover position 1 (left end) and similarly to cover position n. Then the overall time is the maximum of those two? Is that always true? Let's test with an example where expansion on left and right help each other: Suppose line of length 5, r = [100,1,1,1,100]. Starting from s=3 (middle). Step1: interval [3-1,3+1] = [2,4]. Step2: from