Vasya has a pile, that consists of some number of stones. n times he either took one…
- User
Vasya has a pile, that consists of some number of stones. n times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile.
You are given n operations which Vasya has made. Find the minimal possible number of stones that can be in the pile after making these operations. Input
The first line contains one positive integer n — the number of operations, that have been made by Vasya (1 ≤ n ≤ 100).
The next line contains the string s, consisting of n symbols, equal to "-" (without quotes) or "+" (without quotes). If Vasya took the stone on i-th operation, s_i is equal to "-" (without quotes), if added, s_i is equal to "+" (without quotes).
Output
Print one integer — the minimal possible number of stones that can be in the pile after these n operations.
Examples
Input
3
Output
0
Input
4 ++++
Output
4
Input
2 -+
Output
1
Input
5 ++-++
Output
3
Note
In the first test, if Vasya had 3 stones in the pile at the beginning, after making operations the number of stones will be equal to 0. It is impossible to have less number of piles, so the answer is 0. Please notice, that the number of stones at the beginning can't be less, than 3, because in this case, Vasya won't be able to take a stone on some operation (the pile will be empty).
In the second test, if Vasya had 0 stones in the pile at the beginning, after making operations the number of stones will be equal to 4. It is impossible to have less number of piles because after making 4 operations the number of stones in the pile increases on 4 stones. So, the answer is 4.
In the third test, if Vasya had 1 stone in the pile at the beginning, after making operations the number of stones will be equal to 1. It can be proved, that it is impossible to have less number of stones after making the operations.
In the fourth test, if Vasya had 0 stones in the pile at the beginning, after making operations the number of stones will be equal to 3.
Assistant
We need to find minimal possible number of stones that can be in the pile after performing given sequence of operations (n up to 100). Initially there is some unknown number of stones (non-negative integer? "pile, that consists of some number of stones." Usually it's non-negative. But it says the pile was non-empty before each operation of taking one stone. So at any point when we attempt to take a stone, the pile must have at least one stone. So initial number must be such that throughout the sequence, before each '-' operation, the current count is >= 1. We can choose initial number (non-negative integer? Probably >=0. But if initial is 0 and first operation is '-', that would violate because pile empty before taking. So initial must be at least something. So we need to choose initial count x (integer >=0) such that when we simulate, we never get negative? Actually condition: pile non-empty before each operation of taking. So before each '-', count > 0. That means during simulation, count must be at least 1 before performing a '-' operation. After performing '-', count may become 0. Then if next operation is '-', we need count before that operation to be >=1, so after previous operation and before next, count must be >=1. So effectively the running count must never drop below 1 when a '-' is encountered. The final count after all operations is x + (number of '+') - (number of '-') = x + delta, where delta = (#plus - #minus). We need to minimize final count, subject to x >=0? Actually x is initial number of stones. But we can choose any x (presumably non-negative integer) such that the constraint holds. Also we want to minimize final count = x + delta. Since delta is fixed given sequence, minimizing final count is equivalent to minimizing x subject to constraints. So we need to find minimal initial x >=0 such that simulating the sequence never has count < 1 when encountering a '-'.
Let's denote the operations as array s of length n. Let count[0] = x. For i=1..n: before operation i, count_{i-1} must be >= 1 if s_i == '-', because we need non-empty before taking. After performing operation: if s_i == '+', count_i = count_{i-1} + 1; if '-', count_i = count_{i-1} - 1.
We require for each i: if s_i == '-', then count_{i-1} >= 1. That's it.
We need minimal x integer >=0 such that these hold.
We can compute the minimal required initial x by simulating the worst-case deficit. Let's define a running total if starting from 0? But careful: We need to ensure that before each '-', the count is at least 1. We can think of requiring that the minimum prefix count (starting from initial x) never goes below 0? Actually after each operation the count can be 0, but before a '-' it must be >=1. So it's not exactly the typical balance constraint. Let's define net effect of operations: Let delta_i = +1 for '+', -1 for '-'. Then count_i = x + sum_{k=1..i} delta_k. Condition: For each i where s_i == '-', we need count_{i-1} = x + sum_{k=1..i-1} delta_k >= 1.
Thus we need x >= 1 - ( sum_{k=1..i-1} delta_k ) for all i such that s_i = '-'. Also x >= 0 implicitly, but the constraints from '-' might be stronger. So minimal x is max(0, max_{i: s_i='-'} (1 - prefix_sum_{i-1}) ), where prefix_sum_j = sum_{k=1..j} delta_k (with prefix_sum_0 = 0). Then final count = x + sum_{k=1..n} delta_k.
Thus answer = max(0, max_{i: s_i='-'} (1 - prefix_{i-1}) ) + total_delta.
But careful: prefix_{i-1} is sum before operation i. So compute.
Check with examples:
Example1: "---" => operations: -,-,-. delta: -1 each. total_delta = -3. Compute prefixes: i=1, s1='-', prefix_0=0 => need x >= 1-0 =1. i=2, s2='-', prefix_1 = -1 => need x >= 1-(-1)=2. i=3, s3='-', prefix_2 = -2 => need x >= 1-(-2)=3. max =3. x_min=3. final = 3 + (-3)=0. Output 0. matches.
Example2: "++++": total_delta=4. For each operation, there is no '-' so no constraints? Actually s_i are all '+', so set of i with '-' is empty. Then max over empty set is -inf, so x_min = max(0, ... ) =0. final =0+4=4. matches.
Example3: "-+": total_delta = 0? '-' then '+': delta: -1,+1 => total 0. Compute prefixes: i=1, s1='-', prefix_0=0 => need x>=1. i=2 is '+', no constraint. So x_min = max(0,1)=1. final =1+0=1. matches.
Example4: "++-++": operations: +,+,-,+,+. delta: +1,+1,-1,+1,+1 => total = +3. Compute prefixes: prefix_0=0. i=1: '+' -> no constraint. i=2: '+' -> no. i=3: '-' -> prefix_2 = +2 (since +1+1). Need x >= 1-2 = -1 -> no effect (since >=0 anyway). So x_min = 0? Check: If x=0, before operation 3, count after first two: 0+1+1=2, which is >=1, so can take stone -> count becomes 1. Then final =0+3=3. So answer=3 matches.
Thus formula works.
So answer = max(0, max_{i: s_i='-'} (1 - pre[i-1]) ) + total_delta.
But total_delta may be negative? Possibly final count could be negative? But note that we must also ensure that after operations, count is non-negative? The problem statement doesn't explicitly say final count must be non-negative; but pile consists of stones, likely non-negative. Also from constraints, the pile was non-empty before each taking operation; it could become zero after a taking operation, and subsequent operations can be '+' or if there is another '-', it must be non-empty before that. So final count could be zero. But if total_delta is negative and x is minimal subject to constraints, final count might be negative? Let's test: If sequence has more '-' than '+', total_delta negative, but constraints may require x high enough that final count >=0? Possibly final count could be negative? Let's see: Example1: total_delta = -3, x_min=3 => final 0, non-negative. Could there be case where x_min is smaller than needed to keep final non-negative? But final count = x + total_delta. Since constraints only ensure before each '-' count>=1, but after all operations count could be negative? Actually if total_delta is very negative, maybe we need large x to satisfy constraints; but would that guarantee final count >=0? Let's test a scenario: n=1, operation '-': total_delta=-1. Constraint: for i=1: prefix_0=0 => need x>=1. So x_min=1, final=0. So final is non-negative. For n=2: "--": total_delta=-2. Constraints: i=1: need x>=1; i=2: prefix_1 = -1 => need x>=2. So x_min=2 final=0. In general, for a sequence of all '-', x_min = number of '-'? Actually each '-' adds requirement; the strongest is at the last '-' where prefix before is -(k-1), need x>=1-(-(k-1))=k. So x_min = number of '-'. Then total_delta = -k, final = k - k = 0. So final is 0. For mixed sequences, total_delta could be negative but maybe x_min is > -total_delta? Let's see: Suppose sequence: "- - +": operations: -,-,+. total_delta = -1-1+1 = -1. Compute constraints: i=1: need x>=1; i=2: prefix_1 = -1 => need x>=2; i=3: '+' no constraint. So x_min=2, final=2-1=1. So final positive. Could we get final negative? Suppose we have enough pluses earlier to offset the later minuses? But constraints are about prefix before each '-'. So x must be at least the maximum over those of (1 - prefix_before). Since final = x + total_delta. Let's define M = max_{i: s_i='-'} (1 - pre_{i-1}). Then final = max(0, M) + total_delta. But is it always true that final >=0? Possibly not if total_delta is negative and M is small? But note that if there is any '-', M is at least something. Let's attempt to find a case where final <0. We need max(0, M) + total_delta < 0 => total_delta < - max(0, M). Since total_delta = sum of deltas, which includes those minuses. But note that M is derived from prefixes before minuses. For the last operation if it's '-', prefix_before = total_delta (excluding that last minus? Actually if last op is '-', pre_{n-1} = total_delta +1? Let's be careful: total_delta = sum_{k=1..n} delta_k. If last is '-', then delta_n = -1, so pre_{n-1} = total_delta +1. Then constraint for that last '-': x >= 1 - pre_{n-1} = 1 - (total_delta + 1) = - total_delta. So x >= - total_delta. Since total_delta is negative if there are more minuses than pluses? Actually if last op is '-', total_delta could be positive or negative. Let's compute: If total_delta is negative, say total_delta = -5, then x >= -(-5)=5. So x_min >=5. Then final = x + total_delta >=5 -5 =0. So final >=0. If total_delta is positive, then -total_delta is negative, and other constraints might yield positive x. But final = x + positive_delta >= x >0. So final can't be negative. If the last op is '+', we don't have that specific constraint, but maybe total_delta is negative? Then last op is '+', so total_delta = (some negative) because total of deltas negative? Possibly if there are many minuses earlier and pluses later, total_delta could be negative even if last is '+'. Example: "--+": operations: -,-,+ -> total_delta = -1. Constraint strongest: for i=2 '-' prefix_1=-1 => x>=2. x_min=2, final=1>0. Can we have total_delta = -3? Let's try: "- - - + +": ops: -,-,-,+,+ => total_delta = -1. Actually -1-1-1+1+1 = -1. Constraints: for i=3 '-' prefix_2=-2 => x>=3. x_min=3 final=2. So final positive. It seems final always non-negative because the minimal x ensures that after all operations count >=0? Let's prove: For any sequence, with x = max(0, M), we have final = x + total_delta. Consider the last operation. If it's '+', then final = x + total_delta. total_delta = sum deltas. Since the last is '+', we know that after all ops count = x + total_delta. Could it be negative? Suppose x=0 and total_delta negative, but then if total_delta negative, there must be at least one '-', and M might be >0. So x may be >0. In fact, we can show that x >= - total_delta? Not always, but maybe it's guaranteed that M >= - total_delta? Let's test: total_delta = -1, M may be 2 from earlier example. 2 >= 1? Yes. Could we have M < -total_delta? That would mean x_min < -total_delta. But if we set x = M (assuming M>=0), final = M + total_delta. For final to be negative, we need M < -total_delta. But is it possible? Let's try to construct: we need total_delta negative, but constraints not too strong. Suppose we have many pluses early that raise the prefix before minuses, so M might be low. Example: "+++---". Let's compute. Operations: + + + - - - . total_delta = 0? Actually +1+1+1-1-1-1 = 0. So not negative. Try "++--". + + - - : total_delta = 0. "++- - -"? that's 3 plus 3 minus: total_delta 0. To get negative total_delta, we need more minuses than pluses. Consider: "+- - -". Sequence: + - - - . total_delta = +1-1-1-1 = -2. Compute constraints: prefixes: i=1: '+', no; i=2: '-', pre1=+1 => need x>=1-1=0; i=3: '-', pre2=0 => need x>=1-0=1; i=4: '-', pre3=-1 => need x>=1-(-1)=2. So M = max(0,1,2) =2. x_min=2. final=2-2=0. So final=0. What about "++- - - -"? 2 plus, 4 minus: total_delta = 2-4=-2? Actually +1+1-1-1-1-1 = -2. Compute prefixes: i=1:+, i=2:+, i=3: '-' pre2=2 => need x>=1-2=-1 =>0; i=4: '-' pre3=1 => need x>=1-1=0; i=5: '-' pre4=0 => need x>=1-0=1; i=6: '-' pre5=-1 => need x>=1-(-1)=2. So M=2, x_min=2, final=0. Seems pattern: the strongest constraint is from the point where prefix is minimal before a '-'. The minimal prefix before any '-' might be related to total_delta? Actually for final to be negative, we would need that after all operations, count negative, but then at the last operation, if it's '-', the count before it was at least 1, so after subtracting 1, it's >=0. So final count after a '-' is >=0. If last is '+', then count after previous operation could be negative? But if last is '+', then before last op, the count might be negative? But the constraint only applies to '-', not '+'. So is it possible that before a '+', count is negative? Yes, because there is no restriction: we can always add a stone even if pile is empty? The problem statement says: "n times he either took one stone from the pile or added one stone to the pile." It doesn't say we cannot add when pile is empty. Adding one stone to empty pile is fine. So yes, we can add when pile is empty or even negative? Wait, pile consists of some number of stones, but number of stones cannot be negative. So count must always be non-negative, because it's number of stones. Actually physical pile cannot have negative stones. But the problem only explicitly says "The pile was non-empty before each operation of taking one stone from the pile." It does NOT say that the pile could be empty before adding. Typically, you can add stones to an empty pile. So we assume that count must always be >=0, because it's a count of stones. So we must also enforce that the count never goes negative at any point, not just before taking? Actually if count becomes negative, that's impossible physically. But is it implicitly enforced? The operations: "took one stone" - requires at least one stone. "added one stone" - always allowed regardless of current count. But the count can't be negative because you can't have negative stones. So we must also ensure that after any operation, the count is >=0. However, if we ensure before each '-' that count >=1, then after performing '-', count becomes count-1, which would be >=0. So after a '-', it's non-negative automatically. For a '+' operation, count becomes count+1, so if count was >=0, it stays >=0. However, what about the initial state? count0 = x >=0. So if we ensure that before each '-' we have count>=1, then after each '-' we have count>=0, and after each '+' we have count >= previous count +1, but if previous count could be negative? But we haven't ensured that before a '+' count is non-negative. Could it become negative? How? Starting from non-negative x, if we follow operations and always ensure before '-' count>=1, after '-' it's >=0, so at all times after operations we have count>=0. However, what about the state before a '+'? That state is after previous operations, which we argued is >=0. So it's also non-negative. So enforcing the condition for '-' ensures that count never goes negative throughout the process. Because the only operation that could make count negative is '-', and we are preventing that by ensuring count >=1 before it. So no need for explicit extra constraint; it's automatically satisfied.
Thus final count is always non-negative with the minimal x. So answer is always non-negative.
Thus solution: compute prefix sum as we go, maintain max_need = 0. For each i, if s[i] == '-', compute need = 1 - prefix_before (where prefix_before is current prefix sum before this operation). Update max_need = max(max_need, need). Then apply operation to prefix sum (i.e., if '+': prefix += 1; if '-': prefix -= 1). After loop, total_delta = final prefix sum (i.e., after all operations). Then x_min = max(0, max_need). Answer = x_min + total_delta.
But careful: total_delta computed as final prefix sum from starting at 0. That is exactly sum of deltas. So answer = x_min + total_delta.
Implementation: read n, read string s. Initialize prefix = 0, max_need = 0. For i in range(n): if s[i] == '-': need = 1 - prefix; if need > max_need: max_need = need. Then update prefix: if s[i] == '+': prefix += 1 else prefix -= 1. After loop, total_delta = prefix. x_min = max(0, max_need). ans = x_min + total_delta. Print ans.
Test with examples: works.
Edge cases: n=1, s='+' -> max_need stays 0, total_delta=1, ans=1. But is that minimal? Initial x=0, after adding one, final=1. Could initial be negative? No, x>=0. So answer=1 correct. If s='-': need =1-0=1 -> max_need=1, prefix = -1, total_delta=-1, x_min=1, ans=0. correct.
Now check with more random. All good.
But note: In our formula, x_min is max(0, max_{i: s_i='-'} (1 - pre_{i-1})). But pre_{i-1} is computed starting from x=0. That's correct because constraints linear in x: count_before = x + pre_{i-1} (with pre_{i-1} based on starting 0). So need x >= 1 - pre_{i-1}. So indeed the max over those expressions gives minimal x.
Thus answer is straightforward.
Complexity O(n). n <= 100, trivial.
Double-check: Problem statement: "Vasya has a pile, that consists of some number of stones. n times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile." So it's exactly as we modeled.
Now we produce final answer.
But I'll also think if there is any twist: The initial number of stones could be any non-negative integer, and we want minimal possible number after operations. We derived minimal initial gives minimal final because final = initial + delta, delta fixed. So minimizing final is equivalent to minimizing initial. So we need minimal initial satisfying constraints. Yes.
Thus solution done.
We can implement in Python.
Potential pitfalls: The input format has extra spaces? The sample input shows blank lines? Actually in problem statement, they show:
Input
3
Output
0
So there might be an empty line? Usually it's first line n, second line string s. We'll just read normally.
Edge: n up to 100, no issues.
Thus final answer.
Now produce final answer code.
But I want to ensure that max_need might be negative? If all constraints yield need <=0, then max_need may be negative, we then take max(0, negative)=0. That's fine.
Now, check with example where first op is '+' and many pluses: max_need = 0, total_delta = number of pluses, ans = total_delta. But could we choose initial negative to get less? No, because initial must be >=0. So ans is correct.
Thus done.
Now we provide solution.
But the problem asks to print one integer. Good.
Let's write in Python:
def solve(): import sys data = sys.stdin.read().split() if not data: return n = int(data[0]) s = data[1].strip() prefix = 0 max_need = 0 for ch in s: if ch == '-': need = 1 - prefix if need > max_need: max_need = need if ch == '+': prefix += 1 else: # '-' prefix -= 1 total_delta = prefix x_min = max(0, max_need) ans = x_min + total_delta print(ans)
But careful: In loop, after checking need, we update prefix. For '-' we subtract 1; for '+' we add 1. That's correct.
However, note: In loop, after checking ch == '-', we then need to update prefix for both '+' and '-'. We used else that covers '-' only, but what about '+'? So we should use if-else:
for ch in s: if ch == '-': need = 1 - prefix max_need = max(max_need, need) prefix -= 1 else: # '+' prefix += 1
Yes.
Now, let's test with examples:
Example1: s='---' prefix=0, ch='-': need=1-0=1, max_need=1, prefix=-1 ch='-': need=1-(-1)=2, max_need=2, prefix=-2 ch='-': need=1-(-2)=3, max_need=3, prefix=-3 total_delta=-3, x_min=3, ans=0.
Example2: s='++++' prefix=0, ch='+': prefix=1 ch='+': prefix=2 ch='+': prefix=3 ch='+': prefix=4 max_need remains 0, total_delta=4, ans=4.
Example3: s='-+' ch='-': need=1-0=1, max_need=1, prefix=-1 ch='+': prefix=0 (since -1+1=0) total_delta=0, x_min=1, ans=1.
Example4: s='++-++' ch='+': prefix=1 ch='+': prefix=2 ch='-': need=1-2=-1, max_need stays 0? Actually max_need was 0, need=-1, so remains 0, then prefix=1 ch='+': prefix=2 ch='+': prefix=3 total_delta=3, x_min=0, ans=3.
Matches.
Thus solution works.
Now produce final answer.
Potential: There is also interpretation that initial number of stones could be any integer >=0, but we minimized final count. This yields correct.
Now, I'm going to write final solution with explanation.
But note: The problem constraints are small, but our solution is O(n).
Now, write final answer code.
Will also consider using sys.stdin.readline.
Alright. ```python
import sys
def solve() -> None: data = sys.stdin.read().split() if not data: return n = int(data[0]) # n is not really needed, length of string is enough s = data[1].strip()
pref = 0 # prefix sum when starting from 0 max_need = 0 # maximal value of (1 - pref_before) for encountered '-' for ch in s: if ch == '-': # condition for this '‑' : x >= 1 - pref (pref before the operation) need = 1 - pref if need > max_need: max_need = need pref -= 1 else: # '+' pref += 1 total_delta = pref # sum of all operations x_min = max(0, max_need) # minimal allowed initial stones answer = x_min + total_delta # final number of stones print(answer)if name == "main": solve()