def activityNotifications(expenditure, d):
    hist = [0] * 200
    med_l = med_r = math.ceil(d / 2)
    if d % 2 == 0:
        med_r += 1
        
    for i in range(d):
        hist[expenditure[i]] += 1
    
    ans = 0  
    for i in range(d, len(expenditure)):
        events = 0
        curr_l = curr_r = -1
        for j in range(200):
            if curr_l == -1 and events + hist[j] >= med_l:
                curr_l = j
            if curr_r == -1 and events + hist[j] >= med_r:
                curr_r = j
            if curr_l != -1 and curr_r != -1:
                break
            events += hist[j]
 
        if expenditure[i] >= curr_l + curr_r:
            ans += 1
        hist[expenditure[i]] += 1
        hist[expenditure[i - d]] -= 1
        
    return ans

def activityNotifications(expenditure, d):
    # Write your code here
    notifications=0
    
    current_count=[0 for i in range(max(expenditure)+1)]
    
    for n in expenditure[:d]:
        current_count[n]+=1
    
    for i,e in enumerate(expenditure[d:]):
        
        cum_sum=0
        for j,m in enumerate(current_count):
            cum_sum+=m
            if cum_sum>d//2:
                median=j
                break
            elif cum_sum==d/2:
                for k,l in enumerate(current_count[j+1:]):
                    if l!=0:
                        median=(j+(k+j+1))/2
                        break
                break
        print(median,e)
        if e>=(2*median):
            notifications+=1
            
        current_count[e]+=1
        current_count[expenditure[i]]-=1
            
            
    return notifications

function findIndex(array, element) {
  let firstIndex = 0;
  let lastIndex = array.length - 1;
  let indexOfElement;

  while (firstIndex <= lastIndex) {
    const middleIndex = Math.floor((firstIndex + lastIndex) / 2);
    if (array[middleIndex] === element) return middleIndex;

    if (array[middleIndex] > element) {
      lastIndex = middleIndex - 1;
      indexOfElement = middleIndex;
    } else {
      firstIndex = middleIndex + 1;
      indexOfElement = firstIndex;
    }
  }

  return indexOfElement;
}

function activityNotifications(expenditure, d) {
  let notifications = 0;
  const sorted = expenditure.slice(0, d).sort((a, b) => a - b);

  for (let i = d; i < expenditure.length; i++) {
    const median =
      d % 2 === 1
        ? sorted[Math.floor(d / 2)]
        : (sorted[d / 2 - 1] + sorted[d / 2]) / 2;
    if (expenditure[i] >= 2 * median) notifications += 1;

    sorted.splice(findIndex(sorted, expenditure[i - d]), 1);
    sorted.splice(findIndex(sorted, expenditure[i]), 0, expenditure[i]);
  }

  return notifications;
}

public static int activityNotifications(List<Integer> expenditure, int d) {
        var list = new ArrayList<Integer>();
        int notifications = 0;

        Function<List<Integer>, Double> medFunc;
        if (d % 2 == 0) {
            medFunc = (arr) -> ((arr.get(d / 2) + arr.get(d / 2 - 1)) / 2.);
        } else {
            medFunc = (arr) -> (double) arr.get(d / 2);
        }

        var indexToRemove = 0;
        for (var i = 0; i < expenditure.size(); i++) {
            if (i < d) {
                add(expenditure.get(i), list);
            } else {
                double med = medFunc.apply(list);
                if (med * 2 <= expenditure.get(i)) {
                    notifications++;
                }

                if (i < expenditure.size() - 1) {
                    add(expenditure.get(i), list);
                    remove(expenditure.get(indexToRemove), list);
                    indexToRemove++;
                }
            }
        }

        return notifications;
    }

    public static void add(Integer value, List<Integer> list) {
        int index = Collections.binarySearch(list, value);

        // If value is not found, binarySearch returns (-(insertion point) - 1)
        if (index < 0) {
            index = -(index + 1);
        }

        list.add(index, value);
    }

    public static void remove(Integer value, List<Integer> list) {
        int index = Collections.binarySearch(list, value);
        if (index >= 0) {
            list.remove(index);
        }
    }

function activityNotifications(expenditure, d) {
  // Write your code here
  let notificationCounter = 0;
  const middle = Math.ceil(d / 2);
  
  // sort first trailing days, use this as base for future operations and to calculate the median
  const sortedTrailingDays = expenditure
    .slice(0, d)
    .sort((a, b) => (b < a ? 0 : -1));

  for (let i = d; i < expenditure.length; i++) {
    const spentThisDay = expenditure[i];

    if (i > d) { // ignore first iteration, trailings days are sorted once before the loop
      /**
       * 2 operations on the sorted array of trailing day expenditures
       *    1. remove the expenditure of the day that dropped out of the trailing days
       *    2. add the expenditure of the previous day to the trailing days at the correct position
       * 
       * this is way faster than sorting the whole array on every iteration 
       * with the js-array-sort method (as done above the for-loop)
       *  -> this way the function was fast enough to succeed all test-cases, 
       *     even in slow-ass single-CPU-javascript :D
       */
      // remove "dropped out" number/day
      sortedTrailingDays.splice(
        sortedTrailingDays.indexOf(expenditure[i - d - 1]),
        1
      );
      // insert "previous-day-expenditure" to sorted array at the correct position
      const spentDayBefore = expenditure[i - 1];
      if (spentDayBefore <= sortedTrailingDays[0]) {
        sortedTrailingDays.unshift(spentDayBefore); // first pos
      } else if (
        spentDayBefore >= sortedTrailingDays[sortedTrailingDays.length - 1]
      ) {
        sortedTrailingDays.push(spentDayBefore);  // last pos
      } else {
        // find first higher number -> insert there
        const idx = sortedTrailingDays.indexOf(
          sortedTrailingDays.find((n) => n > spentDayBefore) // most likely to slow for testcase-5
        );
        sortedTrailingDays.splice(idx, 0, spentDayBefore);
      }
    }
    
    // calculate median
    const median = d % 2 === 0 ? 
        (sortedTrailingDays[middle] + sortedTrailingDays[middle - 1]) / 2 
        : sortedTrailingDays[middle - 1];

    if (spentThisDay >= median * 2) {
      notificationCounter++;
    }
  }

  return notificationCounter;
}