Compute rightmost-smaller delay times

Given an integer array priorities, define delay[i] as the distance to the rightmost index j > i such that priorities[j] < priorities[i]; if no such index exists, delay[i] = 0. Equal values do not count as smaller. For example, priorities = [8, 2, 11, 4, 9, 4, 7] yields delay = [6, 0, 4, 0, 2, 0, 0] because for 8 the first smaller when scanning from the right is 7 at index 6. Implement a function that computes the entire delay array in better than O(n^ 2) time. State and justify the time and space complexity, and explain how your approach handles duplicates and edge cases (e.g., strictly decreasing or increasing arrays).

Compute Rightmost-Smaller Delay Times

Given an integer array priorities, define delay[i] as the distance to the rightmost index j > i such that priorities[j] < priorities[i]. If no such index exists, delay[i] = 0. Equal values do not count as smaller.\n\nReturn the entire delay array. Aim for better than O(n^2) time.\n\nExample\n\nInput: priorities = [8, 2, 11, 4, 9, 4, 7]\nOutput: [6, 0, 4, 0, 2, 0, 0]\n\nExplanation: For 8 at index 0, scanning from the right the rightmost value smaller than 8 is 7 at index 6, so delay[0] = 6 - 0 = 6. For 11 at index 2 the rightmost smaller value is also 7 at index 6, so delay[2] = 4. For 9 at index 4 it is 7 at index 6, so delay[4] = 2. The value 2 has nothing smaller to its right, and each 4 only sees an equal 4 or larger values (or 7, which is not smaller), so their delays are 0.

Constraints

• 0 <= n <= 10^5
• -10^9 <= priorities[i] <= 10^9
• The array may contain duplicate values; equal values are NOT counted as smaller.
• Must run in better than O(n^2) time.

Hints

1. A naive scan-right per element is O(n^2). You need a structure that answers 'rightmost position with a value below a threshold' quickly.
2. Build a segment tree over positions storing the minimum value in each segment.
3. To find the rightmost qualifying index, descend the tree preferring the right child first; only enter a subtree whose stored minimum is < the query value. This yields the rightmost match in O(log n).
4. Duplicates are handled by the strict '<' comparison: equal values never qualify. Strictly increasing arrays yield all zeros; strictly decreasing arrays yield delay[i] = n-1-i.