import sys # Set higher recursion depth limit for safety, although log N is relatively small # On some platforms like Yukicoder, increasing recursion limit might be necessary. # If this causes issues or is disallowed, it might need removal or adjustment. # sys.setrecursionlimit(200010) def solve(): # Use faster input reading method readline = sys.stdin.readline N, Q = map(int, readline().split()) A = list(map(int, readline().split())) # Coordinate Compression: Map original values to ranks 0 to U-1 # Store unique sorted values to map ranks back to original values unique_vals = sorted(list(set(A))) val_to_rank = {val: i for i, val in enumerate(unique_vals)} rank_to_val = unique_vals U = len(unique_vals) # Number of unique values # Persistent Segment Tree Node definition class Node: # Use __slots__ to potentially reduce memory footprint compared to default dict __slots__ = ('count', 'total_sum', 'left', 'right') def __init__(self, count=0, total_sum=0, left=None, right=None): self.count = count # Number of elements represented by this node self.total_sum = total_sum # Sum of values of elements represented by this node self.left = left # Pointer to left child node self.right = right # Pointer to right child node # roots[i] will store the root of the segment tree representing the prefix A[0...i-1] roots = [None] * (N + 1) # Update function for persistent segment tree (recursive) # Creates a new path of nodes from root to leaf for the updated element # Reuses unchanged subtrees from the previous version def update(node, low, high, target_rank, value): # Initialize current node's properties based on the previous version 'node' current_count = 0 current_total_sum = 0 current_left = None current_right = None if node is not None: # If previous version exists, copy its properties current_count = node.count current_total_sum = node.total_sum current_left = node.left current_right = node.right # Base case: reached a leaf node corresponding to the target rank if low == high: # Create a new leaf node with incremented count and added value return Node(current_count + 1, current_total_sum + value) # Recursive step: determine which child to update mid = (low + high) // 2 new_left = current_left # Initially point to old children new_right = current_right if target_rank <= mid: # Target rank is in the left half, update left child recursively new_left = update(current_left, low, mid, target_rank, value) else: # Target rank is in the right half, update right child recursively new_right = update(current_right, mid + 1, high, target_rank, value) # Calculate new aggregates for the current internal node based on its children # Handle cases where children might be None (representing 0 count/sum) new_count = (new_left.count if new_left else 0) + (new_right.count if new_right else 0) new_total_sum = (new_left.total_sum if new_left else 0) + (new_right.total_sum if new_right else 0) # Create and return the new internal node with updated aggregates and child pointers return Node(new_count, new_total_sum, new_left, new_right) # Build the persistent segment trees version by version # roots[0] is None (representing empty prefix) # roots[i+1] is built upon roots[i] by adding element A[i] if U > 0: # Proceed only if there are unique values (N >= 1 ensures U >= 1) for i in range(N): rank = val_to_rank[A[i]] # Get the rank of the current element A[i] # Create the next version of the tree roots[i+1] = update(roots[i], 0, U - 1, rank, A[i]) # else: if U == 0 (i.e., N=0), this loop is skipped. roots remains all None. # Query function to find the rank of the k-th smallest element in the subarray A[L..R] # Uses two tree roots: roots[R] and roots[L-1] to query the range effectively def query_kth(node_R, node_L_1, low, high, k): # Base case: If we reached a leaf node, its index 'low' is the rank we seek if low == high: return low mid = (low + high) // 2 # Calculate the count of elements in the left child's value range for the subarray A[L..R] # This is done by subtracting counts: count(tree R) - count(tree L-1) left_count_R = node_R.left.count if node_R and node_R.left else 0 left_count_L_1 = node_L_1.left.count if node_L_1 and node_L_1.left else 0 # The difference gives the number of elements in range A[L..R] that fall into the left child's value range left_count_diff = left_count_R - left_count_L_1 if k <= left_count_diff: # The k-th element is within the left subtree's value range. Recurse left. next_node_R = node_R.left if node_R else None next_node_L_1 = node_L_1.left if node_L_1 else None return query_kth(next_node_R, next_node_L_1, low, mid, k) else: # The k-th element is within the right subtree's value range. Recurse right. next_node_R = node_R.right if node_R else None next_node_L_1 = node_L_1.right if node_L_1 else None # Adjust k: We are now looking for the (k - left_count_diff)-th element in the right subtree return query_kth(next_node_R, next_node_L_1, mid + 1, high, k - left_count_diff) # Query function to find the total count and sum of elements with rank <= target_rank in range A[L..R] def query_sum_count(node_R, node_L_1, low, high, target_rank): # If both nodes corresponding to this value range are None, return 0 count and sum if node_R is None and node_L_1 is None: return 0, 0 # Optimization: If the current segment [low, high] is entirely greater than target_rank, contribute nothing if low > target_rank: return 0, 0 # Extract counts and sums from nodes R and L-1, handling None cases count_R = node_R.count if node_R else 0 sum_R = node_R.total_sum if node_R else 0 count_L_1 = node_L_1.count if node_L_1 else 0 sum_L_1 = node_L_1.total_sum if node_L_1 else 0 # If the current segment [low, high] is fully contained within the target range [0, target_rank] if high <= target_rank: # The entire count and sum difference for this node contributes to the result count_diff = count_R - count_L_1 sum_diff = sum_R - sum_L_1 return count_diff, sum_diff # Recursive step: Current segment partially overlaps target range. Explore children. mid = (low + high) // 2 # Query left child next_node_R_left = node_R.left if node_R else None next_node_L_1_left = node_L_1.left if node_L_1 else None res_left = query_sum_count(next_node_R_left, next_node_L_1_left, low, mid, target_rank) # Query right child next_node_R_right = node_R.right if node_R else None next_node_L_1_right = node_L_1.right if node_L_1 else None res_right = query_sum_count(next_node_R_right, next_node_L_1_right, mid + 1, high, target_rank) # Combine results from left and right children return res_left[0] + res_right[0], res_left[1] + res_right[1] # Precompute prefix sums for O(1) retrieval of total sum in any range A[L..R] prefix_sum = [0] * (N + 1) current_sum = 0 for i in range(N): current_sum += A[i] prefix_sum[i+1] = current_sum # Use a list buffer to store results and print all at once using join for efficiency results_buffer = [] # Process Q queries for _ in range(Q): L, R = map(int, readline().split()) # Read query range L, R (1-based) m = R - L + 1 # Number of elements in the range A[L..R] # Calculate the rank of the median. For m elements, median is the ceil(m/2)-th element. k_med = (m + 1) // 2 # Get the roots of the persistent segment trees for the range endpoints root_R = roots[R] root_L_1 = roots[L-1] median_rank = -1 # Default value, indicates issue if U=0 M = 0 # Default median value # Find the median value M if the range is valid and array has elements if U > 0: # Check if there are any unique values (N>=1 guarantees this) # Find the rank (0 to U-1) of the k_med-th element in the subarray median_rank = query_kth(root_R, root_L_1, 0, U - 1, k_med) # Convert the rank back to the actual median value M = rank_to_val[median_rank] # Query count (C_le_M) and sum (Sum_le_M) of elements <= M in range A[L..R] C_le_M, Sum_le_M = 0, 0 # Defaults for empty case U=0 if U > 0 and median_rank != -1: # Ensure median rank was found C_le_M, Sum_le_M = query_sum_count(root_R, root_L_1, 0, U - 1, median_rank) # Calculate total sum (Sum_total) in range A[L..R] using prefix sums Sum_total = prefix_sum[R] - prefix_sum[L-1] # Calculate the minimum value of f(x) using the derived formula: # Min value = M * (2 * C_le_M - m) + Sum_total - 2 * Sum_le_M min_val = M * (2 * C_le_M - m) + Sum_total - 2 * Sum_le_M # Append the calculated minimum value to the results buffer as a string results_buffer.append(str(min_val)) # Print all results, separated by newlines sys.stdout.write("\n".join(results_buffer) + "\n") solve()