Chef and his girlfriend are going to have a promenade. They are walking along the…
- User
Chef and his girlfriend are going to have a promenade. They are walking along the straight road which consists of segments placed one by one. Before walking Chef and his girlfriend stay at the beginning of the first segment, they want to achieve the end of the last segment. There are few problems:
At the beginning Chef should choose constant integer - the velocity of mooving. It can't be changed inside one segment. The velocity should be decreased by at least 1 after achieving the end of some segment. There is exactly one shop on each segment. Each shop has an attractiveness. If it's attractiveness is W and Chef and his girlfriend move with velocity V then if V < W girlfriend will run away into the shop and the promenade will become ruined.
Chef doesn't want to lose her girl in such a way, but he is an old one, so you should find the minimal possible velocity at the first segment to satisfy all conditions. Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of segments. The second line contains N space-separated integers W1, W2, ..., WN denoting the attractiveness of shops.
Output
For each test case, output a single line containing the minimal possible velocity at the beginning.
Constraints
1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 1 ≤ Wi ≤ 10^6
Example Input:
2 5 6 5 4 3 2 5 3 4 3 1 1
Output:
6 5
Explanation Example case 1. If we choose velocity 6, on the first step we have 6 ≥ 6 everything is OK, then we should decrease the velocity to 5 and on the 2nd segment we'll receive 5 ≥ 5, again OK, and so on. Example case 2. If we choose velocity 4, the promanade will be ruined on the 2nd step (we sould decrease our velocity, so the maximal possible will be 3 which is less than 4).
Assistant
We need to interpret the problem. It says: Chef and his girlfriend are going to have a promenade. They are walking along a straight road which consists of segments placed one by one. They start at the beginning of the first segment, want to achieve the end of the last segment.
Rules:
- At the beginning Chef should choose constant integer - the velocity of moving. It can't be changed inside one segment. (Interpretation: For each segment, they move at some constant integer velocity, presumably the same as the chosen velocity at the start of that segment? Actually: "At the beginning Chef should choose constant integer - the velocity of moving. It can't be changed inside one segment." This is ambiguous. Possibly it means: For each segment, Chef chooses a velocity (an integer) that is constant over that segment. But it says "At the beginning Chef should choose constant integer - the velocity of moving." That could refer to the initial velocity? But then it says "It can't be changed inside one segment." That might imply that for each segment, the velocity is constant, but they can change between segments. The second rule: "The velocity should be decreased by at least 1 after achieving the end of some segment." So between segments, the velocity must decrease by at least 1 (i.e., velocity at next segment ≤ previous segment - 1). So we start with an initial velocity V1 for segment 1. Then after finishing segment 1, we reduce velocity to V2 ≤ V1 - 1 for segment 2. After segment 2, reduce to V3 ≤ V2 - 1, and so on. The velocity is an integer.
Additionally, each segment has a shop with attractiveness Wi. If Chef and his girlfriend move with velocity V on that segment, and V < Wi, then girlfriend will run away and the promenade is ruined. So we need V ≥ Wi for each segment i to avoid that.
Chef doesn't want to ruin promenade. So we need to assign velocities V1, V2, ..., VN (integers) such that:
-
V1 is the initial chosen velocity (maybe we need to output minimal possible V1 that allows a feasible sequence? Yes: "find the minimal possible velocity at the first segment to satisfy all conditions.")
-
For i = 1..N, V_i ≥ W_i.
-
V_{i+1} ≤ V_i - 1, for i = 1..N-1 (strictly decreasing by at least 1 each step).
-
Additionally, velocities must be positive? Not explicitly but velocities are positive integers likely. Given Wi ≥ 1, and we need V_i ≥ Wi, so at least 1.
Goal: Find minimal possible V1.
We can think of it as we need a decreasing sequence (strictly decreasing by at least 1) that is at least the given W_i. The minimal V1 is essentially the minimum starting value that can produce such a sequence.
We can view the constraints: For each i, V_i ≥ W_i and also V_i ≤ V_{i-1} - 1. So V_i must be at least W_i, but also at most V_{i-1} - 1. To minimize V1, we would want the sequence to be as low as possible given constraints.
This is a classic problem: Given lower bounds, and a constraint that each subsequent value is at most previous minus 1, minimize the first value. Equivalent to: We need to assign V_i such that V_i ≥ max(W_i, something?). Actually, we can think backwards: We want minimal V1, but V1 must satisfy that there exists a sequence. The constraints are easier to consider from the end: Since V_N ≥ W_N, and V_{N-1} ≥ V_N + 1 (since V_N ≤ V_{N-1} - 1 => V_{N-1} ≥ V_N + 1), and also V_{N-1} ≥ W_{N-1}. So we can propagate a lower bound backwards: Let B_N = W_N. For i from N-1 down to 1: B_i = max(W_i, B_{i+1}+1). Then any feasible sequence must satisfy V_i ≥ B_i, and also we can achieve the lower bounds by setting V_i = B_i (since then V_{i-1} ≥ B_i + 1, we can set V_{i-1} = max(W_{i-1}, B_i+1) which is exactly B_{i-1} if defined recursively). So the minimal possible V1 is B_1. Indeed that yields a feasible sequence: set V_i = B_i, then check V_i ≥ W_i and V_i ≥ B_{i+1}+1 which ensures V_i ≥ B_{i+1}+1, so V_i - 1 ≥ B_{i+1}, so V_{i+1} = B_{i+1} ≤ V_i - 1, satisfying decreasing condition. And it's minimal because any V1 less than B_1 would force either V1 < W1 or after propagation cannot satisfy all lower bounds.
Thus answer for each test case: compute B_1 = max_{?} but easiest: iterate from last to first:
v = W_N for i from N-1 down to 1: v = max(W_i, v+1) // after loop, v is the required minimal V1.
But careful: The decreasing constraint says velocity should be decreased by at least 1 after achieving the end of some segment. That means V2 ≤ V1 - 1, V3 ≤ V2 - 1, etc. So indeed the forward relationship is V_{i+1} ≤ V_i - 1 => V_i ≥ V_{i+1} + 1. So the backwards recurrence is correct.
Therefore the answer is simply the maximum over i of (W_i + (N-i))? Wait: Since B_i = max(W_i, B_{i+1}+1). This can be seen as B_i = max( W_i, W_{i+1}+1, W_{i+2}+2, ..., W_N + (N-i) ). So B_1 = max_{j=1..N} (W_j + (j-1)? Actually careful: For j > i, the term becomes W_j + (j - i). So for i=1, B_1 = max_{j=1..N} (W_j + (j-1)). Because j-i = j-1. So B_1 = max_{j} (W_j + j-1). Let's test with examples.
Example 1: W = [6,5,4,3,2], N=5. Compute: j=1:6+0=6; j=2:5+1=6; j=3:4+2=6; j=4:3+3=6; j=5:2+4=6 => max=6, answer 6. OK.
Example 2: W = [3,4,3,1,1], N=5. Compute: j=1:3+0=3; j=2:4+1=5; j=3:3+2=5; j=4:1+3=4; j=5:1+4=5 => max=5, answer 5. OK.
Thus answer = max_{i=1..N} (W_i + (i-1)). However note that the recurrence gave B_1 = max(W_i + (i-1))? Let's check: B_1 = max_{i} (W_i + (i-1)) indeed. But is there any nuance? Suppose we also need V_i to be integers, which they are. So answer is straightforward.
But wait: Could there be any additional constraint? "At the beginning Chef should choose constant integer - the velocity of moving. It can't be changed inside one segment." Could it be that the velocity is constant across all segments? That would be weird because then "the velocity should be decreased by at least 1 after achieving the end of some segment." contradicts constant across all segments. So the interpretation with decreasing per segment seems correct.
Therefore solution: For each test case, read N, read array W, compute ans = max over i of (W_i + i - 1). Output ans.
Constraints: N up to 10^5, T up to 10, sum N maybe up to 10^5*10? But okay, O(N) per test.
But careful: The index starting from 1? Yes. So compute ans = 0; for i from 1 to N: ans = max(ans, W_i + i - 1). That's it.
Edge cases: N=1, answer = W1 + 0 = W1. That makes sense: initial velocity must be at least W1, and no decrease needed.
Thus solution is trivial.
But is there any possibility that we need to consider that velocity cannot be increased? It only decreases, so the backwards recurrence ensures minimal start. So yes.
Thus final answer.
But before final, let's double-check the problem statement to confirm: "The velocity should be decreased by at least 1 after achieving the end of some segment." Means after finishing a segment, before starting the next segment, the velocity is decreased. So we can have a drop larger than 1? The problem says "decreased by at least 1", so it could be decreased by more, but that would only make the initial velocity possibly higher if we forced a larger drop? Actually if we drop more than needed, we might need higher starting velocity to satisfy later W_i. But to minimize V1, we want to drop exactly 1 each time (if possible) to keep velocities as low as possible. Because dropping more would require earlier V_i to be higher to compensate? Actually consider if we drop more than 1, say V2 = V1 - k with k>1. Then V2 must still be ≥ W2. If we can drop by exactly 1, V2 = V1 -1, that is the maximum possible V2 for a given V1; dropping more reduces V2. To satisfy V2 ≥ W2, we might need V1 to be higher if we drop more. So to minimize V1, we would want to drop as little as possible, i.e., exactly 1 each step, because that yields the largest possible V2, V3,... for a given V1, making it easier to meet the lower bounds. So the minimal V1 is achieved when the decrement is exactly 1 each step. Therefore our recurrence that V_{i+1} = V_i - 1 (the smallest possible decrease) yields minimal V1, but we must also respect V_i ≥ W_i. So indeed the minimal V1 is the max over i of (W_i + (i-1)), assuming we set V_i = V1 - (i-1). However we must also ensure V_i >= W_i, so V1 must be at least W_i + (i-1). This matches.
Thus solution correct.
Now implement in Python.
We'll read T, loop, read N, read list of ints, compute max(W[i] + i). Since i from 0-index, it's W[i] + i (if i is 0-index, then i-1 becomes i? Actually for segment index j (1-indexed), term = W_j + (j-1). If we have array arr with indices 0..N-1 representing j=1..N, then j-1 = index. So answer = max(arr[i] + i). That's even simpler.
Test: Example1: arr=[6,5,4,3,2], i:0..4 => 6+0=6,5+1=6,4+2=6,3+3=6,2+4=6 => max=6. Example2: [3,4,3,1,1] => 3+0=3,4+1=5,3+2=5,1+3=4,1+4=5 => max=5.
Works.
Complexities: O(N) per test.
One more nuance: W_i can be up to 10^6, N up to 10^5, so sum up to ~10^11? Actually W_i + i max is about 10^6+10^5 = 1.01e6, well within 32-bit signed int? 2^31-1 = 2,147,483,647, so safe. But in Python it's arbitrary.
Now answer.
Thus final code:
def solve(): import sys data = sys.stdin.read().strip().split() it = iter(data) t = int(next(it)) out = [] for _ in range(t): n = int(next(it)) max_val = 0 for i in range(n): w = int(next(it)) val = w + i if val > max_val: max_val = val out.append(str(max_val)) sys.stdout.write("\n".join(out))
Check: For N=1, i=0, val=w, max=w, correct.
Edge: Possibly N=0? No, N≥1.
Therefore answer.
But wait: The problem statement: "At the beginning Chef should choose constant integer - the velocity of moving. It can't be changed inside one segment." Could it mean that the velocity is constant across all segments? That interpretation would be: Chef chooses a single integer velocity V at the beginning, and it remains constant throughout the whole promenade (can't change inside a segment nor between segments). Then the rule "The velocity should be decreased by at least 1 after achieving the end of some segment." would make no sense. So it's clear it's per segment.
Thus final solution.
I'll produce final answer with explanation. ```python
import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) max_v1 = 0 for i in range(n): w = int(next(it)) # i is 0‑based, so w + i equals w + (segment_index - 1) val = w + i if val > max_v1: max_v1 = val out_lines.append(str(max_v1)) sys.stdout.write("\n".join(out_lines))
if name == "main": solve()