Why wouldn't on your example ans[1] be 1? If you take the subarray 1 4 2 5, then the element that used to be at 1st position would be in the first half. BTW, you may want to add that you want to compute that for any i, I couldn't infer that until I saw the example

Auto comment: topic has been updated by Usu (previous revision, new revision, compare).

Alright so I have a solution, but I'm pretty tired and wouldn't be at all shocked to see that I overcomplicated it. Let's index the n — k + 1 possible subarrays by their left index (i refers to [i, i + k — 1]).

Let's incrementally activate values in the array in increasing order. When considering an element, we first compute its answer = the number of subarrays that contain it that currently have at least k / 2 activated elements. If we manage to keep track of the subarrays with at least k / 2 activated elements, then we can use a segment tree to update the indices of such subarrays with a +1 and query [pos — k + 1, pos]. It's clear that every subarray will start having at least k / 2 elements from some point till the end, because elements are just getting activated and never being deactivated. Assume you've already determined what's for every subarray the exact point it reaches the k / 2 activated elements. Then all you need to do is to merge these "update subarray" events with the query events.

Now, how to determine when a subarray first reaches the milestone? Well that's given by (k / 2)th smallest element from that range. We can compute that for all subarrays by sweeping from the first one till the last one and keeping a set with the values in the current range, together with the current median. It's easy to initialize it for the first subarray as you can do it in O(KlogK). Then, how to sweep from a subarray to the next one? You just erase an element and insert another one. Comparing the inserted/erased value with the old median tells you whether you should increase or decrease the iterator that pointed to the median, and so you can keep it updated.

It's not terribly difficult to code. The sweeping is just a set and the actual computing of the answer is either a Fenwick tree or a segment tree, both of which are pretty basic. The overall complexity is N(logK+logN) = NlogN (since K can get as large as N I suppose)