How can we solve this question?

We are given an integer N, representing the size of array (Array numbered from 1 to N). Initially, each element of the array is 0.

Now we have to perform T transformations and output the entire transformed array at the end.

Description of each transformation:

Given two integer x and y. For subarray, from 1 to x, we find the minimum element and increment it by one. If there are many elements with the same minimum value, we choose the element with a lower index value. We perform this operation y times.

Sample Input :

7

1

3 5

Sample Output:

2 2 1 0 0 0 0

Explanation:

For N =7, initially array is 0 0 0 0 0 0 0.

For 1 transform say x=3, y=5.

After 1st transformation : 1 0 0 0 0 0 0. (minimum element from 1 to 3 subarray is 0 and minimum index of it is 1).

After 2nd transformation : 1 1 0 0 0 0 0

After 3rd transformation : 1 1 1 0 0 0 0

After 4th transformation : 2 1 1 0 0 0 0

After 5th transformation : 2 2 1 0 0 0 0

Now the problem is, if we apply another transformation, then how can modify the array accordingly? Couldn’t think of anything except the brute force method.

How can we solve this optimally? What will be its time complexity?