import sys from collections import defaultdict def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) S = sys.stdin.readline().strip() # DP state: key is (current_sum, min_sum_end), value is (current_boost, flip_count) dp = defaultdict(lambda: defaultdict(lambda: float('inf'))) # Initial state before any elements are processed dp[0][0] = (0, 0) # (min_sum_end) : (current_boost, flip_count) for i in range(N): new_dp = defaultdict(lambda: defaultdict(lambda: float('inf'))) c = S[i] possibilities = [] if c == '+': possibilities.append(1) elif c == '-': possibilities.append(-1) else: possibilities.extend([1, -1]) for prev_prefix_sum in list(dp.keys()): for prev_min_sum_end in dp[prev_prefix_sum]: current_boost, flip_count = dp[prev_prefix_sum][prev_min_sum_end] current_sum_before = prev_prefix_sum + current_boost for val in possibilities: new_prefix_sum = prev_prefix_sum + val new_min_sum_end = min(val, prev_min_sum_end + val) new_current_sum_before_flip = current_sum_before + val if new_current_sum_before_flip >= 0: new_current_boost = current_boost new_flip_count = flip_count key_new_prefix = new_prefix_sum if new_flip_count < new_dp[key_new_prefix].get(new_min_sum_end, float('inf')): new_dp[key_new_prefix][new_min_sum_end] = (new_current_boost, new_flip_count) else: delta = -2 * new_min_sum_end new_flip_count = flip_count + 1 new_current_boost = current_boost + delta key_new_prefix = new_prefix_sum # Compute new current_sum_after_flip # new_prefix_sum + new_current_boost = (prev_prefix_sum + val) + (current_boost + delta) # = prev_prefix_sum + val + current_boost + delta # but delta = -2 * new_min_sum_end # and new_current_boost = current_boost + delta # So the new_current_sum_after_flip is new_prefix_sum + new_current_boost = new_prefix_sum + current_boost + delta # = (prev_prefix_sum + val) + current_boost + delta # = (prev_prefix_sum + current_boost) + val + delta # = current_sum_before + val + delta # But delta = -2*new_min_sum_end # So current_sum_after_flip = new_current_sum_before_flip + delta # which is (current_sum_before + val) + delta # current_sum_after_flip = (new_current_sum_before_flip) + delta # since new_current_sum_before_flip is prefix_sum_prev + val + current_boost_prev # No need to track, because in the next step, the state is tracked by new_prefix_sum and new_current_boost # So, for the next state, new_prefix_sum is prev_prefix_sum + val # new_current_boost is current_boost + delta # Which contributes to the new current_sum = new_prefix_sum + new_current_boost # Now, we add to new_dp: if new_flip_count < new_dp[key_new_prefix].get(new_min_sum_end, float('inf')): new_dp[key_new_prefix][new_min_sum_end] = (new_current_boost, new_flip_count) dp = new_dp # Now, find the minimal flip_count among all possible states min_flips = float('inf') for prefix in dp: for min_sum in dp[prefix]: current_boost, flip_count = dp[prefix][min_sum] # Check if the final state is valid # The final sum must be prefix + current_boost # Also, all intermediate sums were checked, so no need to re-check if flip_count < min_flips: min_flips = flip_count print(min_flips) if __name__ == "__main__": main()