Every staircase was just one greater than the previous one and it seemed like the sum of first n natural numbers. So the only thing that remained was which of these sums i had to choose. Look, the first good stair is formed with only one square where n = 1, the next one is when n = 3 that is total number of cells are equal to 6 and then the example in the problem statement had n = 7 and hence x = 28. Notice that 3-1 = 2 and 7-3 = 4 hence n is increasing as a power of 2. I tried all cases from n = 1 to n = 7 and only these 3 worked out which gave me more confidence on my intuition.

I found the pattern in the "sum of first n numbers formula" during the contest. I just figured that we have to increase n by a power of 2 in this formula (n*(n+1))/2 and subtract it from x until you run out of cells. I just made this conclusion from the first two good staircases and tried my luck. here's my submission: https://codeforces.me/contest/1419/submission/93215283

Ok. Thanks a lot bro.

Does that mean i just have to set the values of the other elements which are not in the LIS to the minimum possible?

Yes, i know that much.

Can anybody please explain the solution to the problem "Array Sorting". As i am not good with dp, i am not able to understand the editorialist's approach.

thanks a lot bro.