Kuroni and the Score Distribution cf-1305E

Kuroni and the Score Distribution cf-1305E
Adding a number i will increase the count of triplets by ( i -1)/2. Suppose we have elements 1 2 .. adding 3 will increase the count by (3-1)/2=1 because 1+2=3. Now we have 1 2 3, adding 4 to the elements increases the count by (4-1)/2=1 because we have 1+3=4. Generally we take the current most left and the most right elements and add them and we get the new added element and then we take the next most left and the next most right elements and repeat the process. As if we are using two pointers starting from the first index and last index and every time we increment the left pointer and decrement the right pointer, then the sum of the 2 current elements gives us i. having 1 2 3 4 5 6 and then adding 7 , we have 1+6 , 2+5 ,and 3+4 = 3 triplets = (7-1)/2. That's the number of current elements divided by 2 which is the number of elements ( assuming all elements to be 1 2 3 ... i-2 i-1 ) before adding the new element which is i, so the count increases by ( i -1) "the current number of elements before adding i to them" / 2 , because the sum of every two elements gives us i. If you still don't get it or want me to further explain the complete solution, feel free to ask

Let's Say the Number of special triples until now as S (let it be < M). If we add the new number there are two cases

S will still be less than M (in this case we continue to add the new number).

S will be greater than or equal to M.

In the second case, we need to figure out the number which will only add M-S Special triples.

If we use two pointers, First Pointer as 2*(M-S)+1 and second pointer as index of the last number added to the list. Every time we increment the left pointer and decrement the right pointer. The sum of the two elements will always give us a single number M-S times. So will use this number as the next number.