CF2056D Unique Median

An array $ b $ of $ m $ integers is called good if, when it is sorted, $ b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil} $ . In other words, $ b $ is good if both of its medians are equal. In particular, $ \left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil $ when $ m $ is odd, so $ b $ is guaranteed to be good if it has an odd length. You are given an array $ a $ of $ n $ integers. Calculate the number of good subarrays $ ^{\text{∗}} $ in $ a $ . $ ^{\text{∗}} $ An array $ x $ is a subarray of an array $ y $ if $ x $ can be obtained from $ y $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

N/A

N/A

In the first case, every subarray is good since all its elements are equal to $ 1 $ . In the second case, an example of a good subarray is $ b = [10, 2, 3, 3] $ . When it is sorted, $ b = [2, 3, 3, 10] $ , so $ b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3 $ . Another example would be $ b = [1, 10, 2] $ . On the other hand, $ b = [1, 10] $ is not good as its two medians are $ 1 $ and $ 10 $ , which are not equal.