def countPairs(projectCosts, target):
    projectCosts.sort()
    count = 0
    n = len(projectCosts)
    i = 0
    j = 0
    while i < n:
        while j < n and projectCosts[j] - projectCosts[i] <= target:
            j += 1
        count += j - i - 1
        i += 1
    return count

def minimalOperations(words):
    def count_substitutions(word):
        count = 0
        n = len(word)
        i = 0
        while i < n - 1:
            if word[i] == word[i + 1]:
                count += 1
                i += 2
            else:
                i += 1
        return count
    return [count_substitutions(word) for word in words]

def findMinincrease(threadSize):
    n = len(threadSize)
    m = n - 2
    if m <= 0:
        return 0

    groupA_cost = 0
    groupB_cost = 0

    for f in range(2, n):
        index = f - 1
        left = threadSize[index - 1]
        right = threadSize[index + 1]
        target = max(left, right) + 1
        cost = target - threadSize[index]
        if cost < 0:
            cost = 0
        if f % 2 == 0:
            groupA_cost += cost
        else:
            groupB_cost += cost

    if m % 2 == 1:
        return groupA_cost
    else:
        return min(groupA_cost, groupB_cost)

MOD = 10**9 + 7

def comb3(n):
    if n < 3:
        return 0
    return n * (n - 1) % MOD * (n - 2) % MOD * pow(6, MOD - 2, MOD) % MOD

def evenproduct(nums):
    n = len(nums)
    even = sum(1 for num in nums if num % 2 == 0)
    odd = n - even

    total_triplets = comb3(n)
    odd_triplets = comb3(odd)
    
    valid_triplets = (total_triplets - odd_triplets + MOD) % MOD
    
    return valid_triplets

def findMinIncrease(threadSize):
    n = len(threadSize)
    if n < 3:
        return 0

    required_increase = [0] * n
    for i in range(1, n - 1):
        needed = max(threadSize[i - 1], threadSize[i + 1]) + 1
        required_increase[i] = max(0, needed - threadSize[i])

    prev0 = (0, 0)
    prev1 = (-1, 0)

    for i in range(n):
        current0 = (0, 0)
        current1 = (0, 0)

        if i in (0, n - 1):
            current0 = max(prev0, prev1, key=lambda x: (x[0], -x[1]))
            prev0 = current0
            prev1 = (-1, 0)
            continue

        current0 = max(prev0, prev1, key=lambda x: (x[0], -x[1]))

        if prev0[0] != -1:
            current1 = (prev0[0] + 1, prev0[1] + required_increase[i])
        else:
            current1 = (-1, 0)

        prev0 = current0
        prev1 = current1 if current1[0] != -1 else (-1, 0)

    final_ans = max(prev0, prev1, key=lambda x: (x[0], -x[1]))
    return final_ans[1]

def windFarms(premium, x, y):
    n = len(premium)
    mx, my = sum(x[i] * premium[i] for i in range(n)) / sum(premium), sum(y[i] * premium[i] for i in range(n)) / sum(premium)
    cx, cy = round(mx), round(my)
    return sum(premium[i] * (abs(x[i] - cx) + abs(y[i] - cy)) for i in range(n))