import sys import bisect class SegmentTreeNode: def __init__(self, l, r): self.l = l self.r = r self.left = None self.right = None self.sorted_list = [] self.prefix_sums = [] def build(l, r, A): node = SegmentTreeNode(l, r) if l == r: node.sorted_list = [A[l]] node.prefix_sums = [0, A[l]] else: mid = (l + r) // 2 node.left = build(l, mid, A) node.right = build(mid + 1, r, A) # Merge the sorted lists left_list = node.left.sorted_list right_list = node.right.sorted_list node.sorted_list = [] i = j = 0 while i < len(left_list) and j < len(right_list): if left_list[i] < right_list[j]: node.sorted_list.append(left_list[i]) i += 1 else: node.sorted_list.append(right_list[j]) j += 1 node.sorted_list.extend(left_list[i:]) node.sorted_list.extend(right_list[j:]) # Compute prefix sums node.prefix_sums = [0] current_sum = 0 for num in node.sorted_list: current_sum += num node.prefix_sums.append(current_sum) return node def count_query(node, L, R, x): if node.r < L or node.l > R: return 0 if L <= node.l and node.r <= R: return bisect.bisect_right(node.sorted_list, x) return count_query(node.left, L, R, x) + count_query(node.right, L, R, x) def sum_query(node, L, R, x): if node.r < L or node.l > R: return 0 if L <= node.l and node.r <= R: cnt = bisect.bisect_right(node.sorted_list, x) return node.prefix_sums[cnt] return sum_query(node.left, L, R, x) + sum_query(node.right, L, R, x) def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 Q = int(input[ptr]) ptr += 1 A = list(map(int, input[ptr:ptr+N])) ptr += N prefix = [0] * (N + 1) for i in range(N): prefix[i+1] = prefix[i] + A[i] root = build(0, N-1, A) sorted_unique = sorted(set(A)) sorted_unique.sort() for _ in range(Q): L = int(input[ptr]) - 1 ptr += 1 R = int(input[ptr]) - 1 ptr += 1 current_len = R - L + 1 k = (current_len + 1) // 2 low = 0 high = len(sorted_unique) - 1 answer = sorted_unique[-1] while low <= high: mid = (low + high) // 2 x_candidate = sorted_unique[mid] cnt = count_query(root, L, R, x_candidate) if cnt >= k: answer = x_candidate high = mid - 1 else: low = mid + 1 median = answer cnt_less = count_query(root, L, R, median) sum_less = sum_query(root, L, R, median) sum_total = prefix[R+1] - prefix[L] sum_greater = sum_total - sum_less cnt_greater = current_len - cnt_less res = (median * cnt_less - sum_less) + (sum_greater - median * cnt_greater) print(res) if __name__ == "__main__": main()