class FenwickTree:
    def __init__(self, n):
        self.n    = n
        self.tree = [0] * (n + 1)   # 1-indexed

    def update(self, i, delta):
        """Add delta to position i (1-indexed)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i             # move to parent

    def prefix_sum(self, i):
        """Sum of elements from index 1 to i (inclusive)."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i             # strip lowest set bit → move to predecessor
        return total

    def range_sum(self, l, r):
        """Sum of elements from l to r (1-indexed, inclusive)."""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

    @classmethod
    def from_array(cls, nums):
        """Build in O(n) — prefer over n individual updates."""
        n  = len(nums)
        ft = cls(n)
        for i, v in enumerate(nums, 1):
            ft.tree[i] += v
            parent = i + (i & -i)
            if parent <= n:
                ft.tree[parent] += ft.tree[i]
        return ft


# Usage
ft = FenwickTree.from_array([3, 2, -1, 6, 5, 4, -3, 3, 7, 2])
print(ft.prefix_sum(5))    # 3+2-1+6+5 = 15
print(ft.range_sum(2, 7))  # 2-1+6+5+4-3 = 13
ft.update(3, 4)            # add 4 at index 3 (0-indexed: 2)
print(ft.prefix_sum(5))    # now 19

# Count inversions in O(n log n): for each element, query how many
# previously seen elements are greater (= prefix_sum(n) - prefix_sum(val)).

def count_inversions(nums):
    # Coordinate compress to [1..n]
    rank = {v: i+1 for i, v in enumerate(sorted(set(nums)))}
    n    = len(rank)
    ft   = FenwickTree(n)

    inversions = 0
    for x in nums:
        r = rank[x]
        inversions += ft.prefix_sum(n) - ft.prefix_sum(r)   # count elements > x seen so far
        ft.update(r, 1)

    return inversions

# count_inversions([3, 1, 2]) → 2  (pairs: (3,1), (3,2))

class BIT2D:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]

    def update(self, r, c, delta):
        i = r
        while i <= self.rows:
            j = c
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & -j
            i += i & -i

    def prefix_sum(self, r, c):
        total = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                total += self.tree[i][j]
                j -= j & -j
            i -= i & -i
        return total

    def range_sum(self, r1, c1, r2, c2):
        return (self.prefix_sum(r2, c2)
                - self.prefix_sum(r1 - 1, c2)
                - self.prefix_sum(r2, c1 - 1)
                + self.prefix_sum(r1 - 1, c1 - 1))