Design faster delay-time computation

You are given an array of integers representing task priorities. Tasks execute from right to left. For each index i, define its delay time as j - i where j is the largest index > i such that priorities[j] < priorities[i] (i.e., the rightmost strictly smaller element to the right); if no such j exists, the delay time is 0. Return the delay time array for all indices. Example: for [8,2,11,4,9,4,7], the result is [6,0,4,0,2,0,0] (for 8 at index 0, the first smaller when scanning from the far right is 7 at index 6, so delay time is 6). Design an algorithm faster than O(n^ 2); describe your data structures, analyze time and space complexity, and implement the solution. Handle duplicates and large inputs.

Design faster delay-time computation

You are given an array of integers priorities representing task priorities. Tasks execute conceptually from right to left. For each index i, define its delay time as j - i, where j is the largest index j > i such that priorities[j] < priorities[i] (i.e., the rightmost strictly-smaller element to the right of i). If no such j exists, the delay time is 0. Return the array of delay times for every index.

Example: for [8, 2, 11, 4, 9, 4, 7] the answer is [6, 0, 4, 0, 2, 0, 0]. For the 8 at index 0, scanning from the far right the first element strictly smaller than 8 is 7 at index 6, so its delay time is 6 - 0 = 6.

Design an algorithm faster than O(n^2). Describe your data structures, analyze time and space complexity, and handle duplicates and large inputs.

Approach (O(n log n)): Coordinate-compress the values to dense ranks. Build a segment tree indexed by rank that stores, for each rank bucket, the maximum array index inserted so far. Process the array from right to left; before inserting index i, query the tree over all ranks strictly less than rank(priorities[i]) for the maximum stored index — that is the rightmost smaller element to the right. The delay time is (that index) - i (or 0 if the query returns nothing). Then insert (rank(priorities[i]) -> i) and continue.

Constraints

• 1 <= n <= 2 * 10^5 (large inputs must be handled; O(n^2) brute force times out)
• -10^9 <= priorities[i] <= 10^9
• Duplicate values are allowed; equal values do NOT count as 'strictly smaller'
• The delay time is based on the LARGEST (rightmost) qualifying index, not the nearest

Hints

1. Brute force is O(n^2): for each i scan all the way to the end for the rightmost smaller value. To beat it, avoid re-scanning by processing indices right-to-left and reusing a data structure keyed by value.
2. Coordinate-compress values to dense ranks so you can index a segment tree by rank instead of by raw value (values can be up to 10^9 and negative).
3. Maintain a segment tree over ranks where each leaf holds the maximum array index inserted so far for that rank. Processing right-to-left guarantees the tree only contains indices greater than the current i.
4. For index i, query the tree over the range of ranks [0, rank(priorities[i]) - 1] for the maximum stored index. That maximum index is the rightmost strictly-smaller element to the right; subtract i to get the delay (0 if the query is empty).