You are given a $0$ indexed integer array obstacles of length n, where obstacles[i] represents the height of the $i^{ ext{th}}$ obstacle.

For every index i from $0$ to n - 1, determine the length of the longest obstacle course that ends at index i satisfying the following conditions:

• You select a sequence of obstacles with indices between $0$ and i, inclusive.

• You must include the $i^{ ext{th}}$ obstacle in the chosen course.

• The relative order of the selected obstacles must match their original order in obstacles.

• The height of each chosen obstacle must be greater than or equal to the height of the preceding chosen obstacle.

Return an integer array ans of length n, where ans[i] is the maximum length of a valid obstacle course ending at index i.

Constraints:

• n == obstacles.length

• $1 \leq$ n $\leq 10^5$

• $1 \leq$ obstacles[i] $\leq 10^7$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.