One way of calculating the score is to, whenever you insert an element, calculate the amount of pairs immediately created by that point that satisfy the condition. At a given point in time when you push some element to the front or to the back of the deque, it is either behind all existing elements or ahead of all existing elements. You can represent the value immediately created by point $$$i$$$ by pushing it to the front as $$$A_i$$$ and the value pushing it to the back as $$$B_i$$$. To calculate these values, you could use a segment tree (and maybe index compression if the values are large).

Once you have values of $$$(A_i,B_i)$$$ calculated, the problem now becomes choosing $$$M$$$ elements whose $$$A$$$ value is added to the result and choosing $$$K$$$ elements whose $$$B$$$ values are added to the result. One way you could do this is to initially sum up all of the $$$A$$$ values for every element and put it into the result. Now, to add $$$B$$$ values, we will choose $$$K$$$ elements and add $$$B_i-A_i$$$ to the result. To make those choices optimal, sort by the values of $$$B_i-A_i$$$ and add the $$$K$$$ highest values.

This would run in $$$O(nlog(n))$$$ time.