thanks, by the way in editorial they say that p=1-min_val where min_val==min value in prefix sum of q[i].
so i don’t understand this part…if you can please elaborate this a little.
If p = 1-p'[r] such that p'[r] is not the minimum and let p'[x] be the minimum prefix sum. From the editorial, p[i] = p + p'[i]. Substitute in the values,
p[x] = 1 - p'[r] + p'[x] which will be less than 1.
But since the minimum value needs to be 1, this cannot be possible. Thus, p'[r] = p'[x], the minimum value of the prefix sum.
okay…still i don’t understand how can we say this…?-> If p = 1-p’[r]
i know this should not be less than 1…and greater than n.