Lexicographically smallest generated array

Problem Given arr of length n and bounds [l, r], build brr with: l <= brr[i] <= r; brr non-decreasing (brr[i] <= brr[i+1]); and the differences strictly increasing (brr[i] − arr[i] < brr[i+1] − arr[i+1]). Return the lexicographically smallest valid brr, or [-1].

Input / Output

• Input: int[] arr, ints l, r. Output: int[] brr or [-1].

Constraints

• n up to 10^5; O(n) greedy expected.

Example

• arr = [1,2,2], l = 2, r = 5: choose brr[0]=2 (diff 1); need diff > 1 at i=1 → brr[1] >= 4 (diff 2) and >= brr[0] → 4; i=2 needs diff > 2 → brr[2] >= 5 (diff 3) → [2,4,5].

Expected approach

• Greedy smallest-feasible per position: track prevVal and prevDiff; candidate = max(l, prevVal, arr[i] + prevDiff + 1); if candidate > r → [-1]; assign and update. Lexicographic minimality follows because taking the smallest feasible value never blocks later positions more than any larger choice (both later constraints are monotone in current value/diff) — sketch that argument. O(n)/O(1). Off-by-one on the STRICT diff inequality is the trap.