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] if none exists.

Input / Output

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

Constraints

• n up to 10^5; an O(n) greedy is expected.
• The difference inequality is STRICT.

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].