import sys # Fenwick Tree (Binary Indexed Tree) Implementation # Uses 1-based indexing internally. Tree stores values for indices 1 through size. class FenwickTree: """ A Fenwick Tree (Binary Indexed Tree) supporting point updates and prefix sum queries. It uses 1-based indexing internally for array access, but methods accept standard indices. """ def __init__(self, size): """ Initializes a Fenwick Tree supporting indices up to `size`. The internal tree array will have size `size + 1`. """ # The internal array size needs to be size + 1 to handle index `size`. self.tree = [0] * (size + 1) def update(self, k, delta): """ Adds `delta` to the value at index `k`. Assumes `k` is 1-based index. """ # Ensure k is within the valid range [1, size] if k <= 0: # Index must be positive for 1-based indexing. # Depending on context, might raise error or silently ignore. # Let's ignore for robustness against potential edge cases like time 0. return _size = len(self.tree) while k < _size: self.tree[k] += delta # Move to the next index that k contributes to k += k & (-k) def query(self, k): """ Computes the prefix sum up to index `k` (sum of values for indices 1, 2, ..., k). Assumes `k` is 1-based index. """ # If k is 0 or less, the prefix sum is 0. if k <= 0: return 0 # Ensure k does not exceed the maximum index supported by the tree structure. _size = len(self.tree) # Clamp k to the maximum valid index if it's too large. k = min(k, _size - 1) s = 0 while k > 0: s += self.tree[k] # Move to the index responsible for the next lower range k -= k & (-k) return s def solve(): """ Main function to solve the problem. Reads input, processes events, and prints output. """ N = int(sys.stdin.readline()) L_str = sys.stdin.readline().split() L = [int(x) for x in L_str] T = int(sys.stdin.readline()) # Map problem characters ('A', 'B', ...) to their levels (scores) problem_levels = {} for i in range(N): problem_char = chr(ord('A') + i) problem_levels[problem_char] = L[i] # Calculate the maximum possible score a participant can achieve. # This is the sum of all problem levels. max_score_actual = sum(L) # Dictionary to store the state of each participant. # Key: participant name (str) # Value: dictionary {'score': int, 'time': int, 'solved': set} # 'score' is the total score. # 'time' is the timestamp of the last submission that increased the score. # 'solved' is a set of problem characters solved by the participant. participants = {} # Fenwick tree to store counts of participants for each score value. # It supports scores from 0 up to max_score_actual. # We use 1-based indexing for the Fenwick tree: score `s` corresponds to index `s + 1`. # The size needed is max_score_actual + 1 to support the index for the maximum score. score_count_tree = FenwickTree(max_score_actual + 1) # A list where each element is a Fenwick tree. # score_time_trees[s] is a Fenwick tree managing submission times for participants currently having score `s`. # This list is indexed directly by score `s` (from 0 to max_score_actual). # Each time-based Fenwick tree supports times from 1 up to T. The size needed is T. score_time_trees = [FenwickTree(T) for _ in range(max_score_actual + 1)] results = [] # List to store the ranks calculated for query ('?') operations. # Process events chronologically from time 1 to T. for current_time in range(1, T + 1): line = sys.stdin.readline().split() name = line[0] action = line[1] # Either a problem character ('A', 'B', ...) or '?' if action == '?': # This is a query for the rank of participant 'name'. # The problem constraints guarantee that 'name' must exist in 'participants' # because a query is only made if the participant has made at least one submission before. my_state = participants[name] my_score = my_state['score'] my_time = my_state['time'] # Calculate the rank based on score and time: # Rank = 1 + (number of participants strictly better than 'name') # A participant 'other' is strictly better if: # other_score > my_score # OR (other_score == my_score AND other_time < my_time) # Count participants with score > my_score: # This is (Total number of participants tracked) - (Number of participants with score <= my_score) # Total participants tracked = score_count_tree.query(max_score_actual + 1) # Participants with score <= my_score = score_count_tree.query(my_score + 1) (using 1-based index for score) count_better_score = score_count_tree.query(max_score_actual + 1) - score_count_tree.query(my_score + 1) # Count participants with score == my_score and time < my_time: # Query the Fenwick tree specific to 'my_score' (score_time_trees[my_score]). # We need the sum of counts for times from 1 up to 'my_time - 1'. count_same_score_better_time = score_time_trees[my_score].query(my_time - 1) # The rank is 1 plus the total count of better participants. rank = count_better_score + count_same_score_better_time + 1 results.append(str(rank)) else: # This is a submission event for problem 'action' by participant 'name'. problem_char = action # Retrieve the level (score) for the submitted problem. # Based on constraints, problem_char will be a valid problem ID. problem_level = problem_levels[problem_char] is_state_updated = False # Flag to check if this submission changes the participant's state if name in participants: # Participant already exists in the system. current_state = participants[name] # Check if this problem has already been solved by this participant. # The problem constraints state that duplicate submissions (Name, P) don't occur. # However, this check is robust. if problem_char not in current_state['solved']: # This is a new problem solved by this participant. Update their state. is_state_updated = True # Store the old state before update, needed for Fenwick Tree adjustments. old_score = current_state['score'] old_time = current_state['time'] # Calculate the new state after solving this problem. new_score = old_score + problem_level new_time = current_time # The time of this event is the new last update time. # Update the participant's record in the dictionary. current_state['solved'].add(problem_char) current_state['score'] = new_score current_state['time'] = new_time # Update Fenwick Trees to reflect the state change: # 1. Remove the contribution of the old state. score_count_tree.update(old_score + 1, -1) # Decrement count for old score (1-based index) score_time_trees[old_score].update(old_time, -1) # Remove old time from the tree for old score # 2. Add the contribution of the new state. score_count_tree.update(new_score + 1, 1) # Increment count for new score (1-based index) score_time_trees[new_score].update(new_time, 1) # Add new time to the tree for new score else: # This is the first submission for this participant 'name'. is_state_updated = True # Calculate the initial state after this first submission. new_score = problem_level new_time = current_time # Add the new participant's record to the dictionary. participants[name] = {'score': new_score, 'time': new_time, 'solved': {problem_char}} # Update Fenwick Trees to add the new participant's state: # Increment count for the new score (1-based index) score_count_tree.update(new_score + 1, 1) # Add the submission time to the time tree for the new score score_time_trees[new_score].update(new_time, 1) # If is_state_updated is False, it means the participant submitted a problem they had already solved. # In this scenario, their score and last submission time do not change, and no updates to Fenwick trees are needed. # After processing all T events, print the collected results for all queries. # Each result should be on a new line. print("\n".join(results)) # Execute the main function to run the solution. solve()