def getMinConnectionCost(warehouseCapacity, additionalHubs):
    n = len(warehouseCapacity)
    q = len(additionalHubs)
    result = []
 
    # Pre-calculate prefix sums and costs to central hub
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + warehouseCapacity[i]
 
    # Pre-calculate total cost to central hub
    total_to_n = 0
    for i in range(n-1):
        total_to_n += warehouseCapacity[n-1] - warehouseCapacity[i]
 
    for hubs in additionalHubs:
        hubA, hubB = hubs[0] - 1, hubs[1] - 1  # Convert to 0-based indexing
 
        # Calculate costs using prefix sums
        total_cost = 0
 
        # Segment 1: Before hubA
        if hubA > 0:
            count = hubA
            total_cost += count * warehouseCapacity[hubA] - (prefix_sum[hubA] - prefix_sum[0])
 
        # Segment 2: Between hubA and hubB
        if hubB > hubA + 1:
            count = hubB - (hubA + 1)
            total_cost += count * warehouseCapacity[hubB] - (prefix_sum[hubB] - prefix_sum[hubA + 1])
 
        # Segment 3: After hubB to before n
        if hubB < n-2:
            total_cost += total_to_n - (prefix_sum[n-1] - prefix_sum[hubB + 1]) - \
                         (n-2 - hubB) * warehouseCapacity[n-1]
 
        result.append(total_cost)
 
    return result
 
# Test cases
def test():
    # Sample Case 0
    warehouseCapacity0 = [0, 2, 5, 9, 12, 18]
    additionalHubs0 = [[2, 5], [1, 3]]
    print(getMinConnectionCost(warehouseCapacity0, additionalHubs0))  # Expected: [12, 18]
 
    # Sample Case 1
    warehouseCapacity1 = [2, 6, 8, 14]
    additionalHubs1 = [[1, 2]]
    print(getMinConnectionCost(warehouseCapacity1, additionalHubs1))  # Expected: [6]
 
if __name__ == "__main__":
    test()

ZGVmIGdldE1pbkNvbm5lY3Rpb25Db3N0KHdhcmVob3VzZUNhcGFjaXR5LCBhZGRpdGlvbmFsSHVicyk6CiAgICBuID0gbGVuKHdhcmVob3VzZUNhcGFjaXR5KQogICAgcSA9IGxlbihhZGRpdGlvbmFsSHVicykKICAgIHJlc3VsdCA9IFtdCiAgICAKICAgICMgUHJlLWNhbGN1bGF0ZSBwcmVmaXggc3VtcyBhbmQgY29zdHMgdG8gY2VudHJhbCBodWIKICAgIHByZWZpeF9zdW0gPSBbMF0gKiAobiArIDEpCiAgICBmb3IgaSBpbiByYW5nZShuKToKICAgICAgICBwcmVmaXhfc3VtW2kgKyAxXSA9IHByZWZpeF9zdW1baV0gKyB3YXJlaG91c2VDYXBhY2l0eVtpXQogICAgCiAgICAjIFByZS1jYWxjdWxhdGUgdG90YWwgY29zdCB0byBjZW50cmFsIGh1YgogICAgdG90YWxfdG9fbiA9IDAKICAgIGZvciBpIGluIHJhbmdlKG4tMSk6CiAgICAgICAgdG90YWxfdG9fbiArPSB3YXJlaG91c2VDYXBhY2l0eVtuLTFdIC0gd2FyZWhvdXNlQ2FwYWNpdHlbaV0KICAgIAogICAgZm9yIGh1YnMgaW4gYWRkaXRpb25hbEh1YnM6CiAgICAgICAgaHViQSwgaHViQiA9IGh1YnNbMF0gLSAxLCBodWJzWzFdIC0gMSAgIyBDb252ZXJ0IHRvIDAtYmFzZWQgaW5kZXhpbmcKICAgICAgICAKICAgICAgICAjIENhbGN1bGF0ZSBjb3N0cyB1c2luZyBwcmVmaXggc3VtcwogICAgICAgIHRvdGFsX2Nvc3QgPSAwCiAgICAgICAgCiAgICAgICAgIyBTZWdtZW50IDE6IEJlZm9yZSBodWJBCiAgICAgICAgaWYgaHViQSA+IDA6CiAgICAgICAgICAgIGNvdW50ID0gaHViQQogICAgICAgICAgICB0b3RhbF9jb3N0ICs9IGNvdW50ICogd2FyZWhvdXNlQ2FwYWNpdHlbaHViQV0gLSAocHJlZml4X3N1bVtodWJBXSAtIHByZWZpeF9zdW1bMF0pCiAgICAgICAgCiAgICAgICAgIyBTZWdtZW50IDI6IEJldHdlZW4gaHViQSBhbmQgaHViQgogICAgICAgIGlmIGh1YkIgPiBodWJBICsgMToKICAgICAgICAgICAgY291bnQgPSBodWJCIC0gKGh1YkEgKyAxKQogICAgICAgICAgICB0b3RhbF9jb3N0ICs9IGNvdW50ICogd2FyZWhvdXNlQ2FwYWNpdHlbaHViQl0gLSAocHJlZml4X3N1bVtodWJCXSAtIHByZWZpeF9zdW1baHViQSArIDFdKQogICAgICAgIAogICAgICAgICMgU2VnbWVudCAzOiBBZnRlciBodWJCIHRvIGJlZm9yZSBuCiAgICAgICAgaWYgaHViQiA8IG4tMjoKICAgICAgICAgICAgdG90YWxfY29zdCArPSB0b3RhbF90b19uIC0gKHByZWZpeF9zdW1bbi0xXSAtIHByZWZpeF9zdW1baHViQiArIDFdKSAtIFwKICAgICAgICAgICAgICAgICAgICAgICAgIChuLTIgLSBodWJCKSAqIHdhcmVob3VzZUNhcGFjaXR5W24tMV0KICAgICAgICAKICAgICAgICByZXN1bHQuYXBwZW5kKHRvdGFsX2Nvc3QpCiAgICAKICAgIHJldHVybiByZXN1bHQKCiMgVGVzdCBjYXNlcwpkZWYgdGVzdCgpOgogICAgIyBTYW1wbGUgQ2FzZSAwCiAgICB3YXJlaG91c2VDYXBhY2l0eTAgPSBbMCwgMiwgNSwgOSwgMTIsIDE4XQogICAgYWRkaXRpb25hbEh1YnMwID0gW1syLCA1XSwgWzEsIDNdXQogICAgcHJpbnQoZ2V0TWluQ29ubmVjdGlvbkNvc3Qod2FyZWhvdXNlQ2FwYWNpdHkwLCBhZGRpdGlvbmFsSHViczApKSAgIyBFeHBlY3RlZDogWzEyLCAxOF0KICAgIAogICAgIyBTYW1wbGUgQ2FzZSAxCiAgICB3YXJlaG91c2VDYXBhY2l0eTEgPSBbMiwgNiwgOCwgMTRdCiAgICBhZGRpdGlvbmFsSHViczEgPSBbWzEsIDJdXQogICAgcHJpbnQoZ2V0TWluQ29ubmVjdGlvbkNvc3Qod2FyZWhvdXNlQ2FwYWNpdHkxLCBhZGRpdGlvbmFsSHViczEpKSAgIyBFeHBlY3RlZDogWzZdCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgdGVzdCgp