Today, Mezo is playing a game. Zoma, a character in that game, is initially at position…
- User
Today, Mezo is playing a game. Zoma, a character in that game, is initially at position x = 0. Mezo starts sending n commands to Zoma. There are two possible commands:
- 'L' (Left) sets the position x: =x - 1;
- 'R' (Right) sets the position x: =x + 1.
Unfortunately, Mezo's controller malfunctions sometimes. Some commands are sent successfully and some are ignored. If the command is ignored then the position x doesn't change and Mezo simply proceeds to the next command.
For example, if Mezo sends commands "LRLR", then here are some possible outcomes (underlined commands are sent successfully):
- "LRLR" — Zoma moves to the left, to the right, to the left again and to the right for the final time, ending up at position 0;
- "LRLR" — Zoma recieves no commands, doesn't move at all and ends up at position 0 as well;
- "LRLR" — Zoma moves to the left, then to the left again and ends up in position -2.
Mezo doesn't know which commands will be sent successfully beforehand. Thus, he wants to know how many different positions may Zoma end up at. Input
The first line contains n (1 ≤ n ≤ 10^5) — the number of commands Mezo sends.
The second line contains a string s of n commands, each either 'L' (Left) or 'R' (Right).
Output
Print one integer — the number of different positions Zoma may end up at.
Example
Input
4 LRLR
Output
5
Note
In the example, Zoma may end up anywhere between -2 and 2.
Assistant
We need to solve the problem: given a sequence of n commands (each either L or R), where some subset of commands may be ignored (i.e., not executed), but the order is fixed: for each command, if it is not ignored, we apply it; if ignored, skip. Essentially, we start at 0 and apply a subsequence (in order) of the commands. The resulting final position is the sum over executed commands: +1 for R, -1 for L. We want to count the number of distinct possible final positions.
This is reminiscent of: given a multiset of +1 and -1, what are possible sums of any subset? That is the set of all possible sums of a subsequence, but note that the order doesn't matter for sum; only which commands are executed. Since we can choose any subset (each command can be either executed or ignored), the set of possible final positions is exactly the set of all sums of any subset of the n steps, where each step contributes +1 if R, -1 if L. This is the same as: given integers a_i = 1 if R, -1 if L, we can choose any subset S of {1..n}, final position = sum_{i in S} a_i.
But is there any restriction? The subset must be in order? The sum doesn't depend on order; any subset yields some sum, and we can achieve any subset because we can decide independently per command whether to ignore it. Yes, each command is independent: we can choose for each command to include or not. So the set of possible sums is the set of all possible sums of the multiset of +1 and -1. This is like: given p = count of R, q = count of L, so the net sum if we take all is p - q. But we can take any subset, so the possible sums are all integers from -(q) + (0?) Actually, let's think: if we take some number of R and some number of L. Let i be number of Rs executed, j be number of Ls executed, then sum = i - j, where 0 ≤ i ≤ p, 0 ≤ j ≤ q. So the set S = { i - j | 0 ≤ i ≤ p, 0 ≤ j ≤ q }. That set is all integers from -q to p? Not exactly; because i - j can take values from -q (when i=0, j=q) to p (when i=p, j=0). But are all integers in between achievable? Possibly, but there might be parity or step constraints? For example, if we have only Rs (q=0), then possible sums are i where i from 0 to p, all integers; similarly only Ls gives from -q to 0. When both R and L are present, we can combine. For given i and j, i - j. As i varies from 0..p and j from 0..q, the set of differences is essentially all integers d such that there exist i,j with d = i - j. This is equivalent to: for any integer d, we need to see if there exist i,j with 0≤i≤p, 0≤j≤q, d = i - j. This can be rewritten as i = d + j, and i must be between 0 and p, j between 0 and q. So we need j such that 0 ≤ j ≤ q and 0 ≤ d+j ≤ p. So existence if there exists j with max(0, -d) ≤ j ≤ min(q, p-d). Actually, we need j satisfying both: j ≥ 0, j ≤ q, and j ≥ -d? Because i = d+j ≥0 => j ≥ -d; and i ≤ p => d+j ≤ p => j ≤ p - d. So we need j satisfying max(0, -d) ≤ j ≤ min(q, p-d). For such j to exist, we need max(0, -d) ≤ min(q, p-d). That condition holds for d in range -q ≤ d ≤ p, but is it always? Let's test extremes: d = -q: then max(0, -(-q)=q) = q, min(q, p - (-q)= p+q) = q, so equality, okay. d = p: max(0, -p) = 0 (since -p ≤0), min(q, p-p=0)=0, okay. For d in between, we need to check if there is always an integer j. The interval length is min(q, p-d) - max(0, -d). For example, p=1,q=1: d=0: max(0,0)=0, min(1,1)=1, so exists j; d=1: max(0,-1)=0, min(1,0)=0 => j=0 works; d=-1: max(0,1)=1, min(1,2)=1 => j=1 works. So all integers from -1 to 1. p=2,q=2: d from -2 to 2 all exist. But what about p=2,q=1? d range: -1 to 2. Check d=0: max(0,0)=0, min(1,2)=1 => exists; d=1: max(0,-1)=0, min(1,1)=1 => exists; d=2: max(0,-2)=0, min(1,0)=0 => exists; d=-1: max(0,1)=1, min(1,3)=1 => exists. So all integers in that range are achievable. But is there any case where some integer within [-q, p] is not achievable? Suppose p=0,q=1 => range [-1,0] both exist. Suppose p=1,q=0 => [0,1]. So seems always all integers in that inclusive range are achievable. Because we can adjust i and j independently. But is there any parity restriction? Since i and j are independent, difference i-j can be any integer between -q and p because you can set j = min(q, something) and i = d+j, but need integer. As long as there exists an integer j satisfying constraints, it's fine. The condition max(0,-d) ≤ min(q, p-d) is necessary and sufficient. For d in [-q, p], we can check: if d≥0, then max(0,-d)=0, min(q, p-d) =? Since d≤p, p-d≥0, so min(q, p-d) ≥0. Need 0 ≤ min(q, p-d) which is always true. So there is always j=0 feasible? Wait: j=0 is only feasible if i = d, and i must be ≤ p and ≥0. For d≥0, i = d, and we require d ≤ p (true because d≤p) and d≥0 (true). So j=0 works! So for d≥0, we can simply take j=0, i=d, provided d ≤ p. And d≥0. So all non-negative d up to p are achievable. For d negative, we can take i=0, j = -d. Then need -d ≤ q and -d ≥0, which holds if -d ≤ q, i.e., d ≥ -q. So for d negative, set i=0, j = -d. So all negative d down to -q are achievable. Thus indeed the set of possible sums is all integers from -q to p inclusive. So answer would be p + q + 1? Since -q to p inclusive has length (p - (-q) + 1) = p+q+1 = n+1. That suggests answer always n+1? But example n=4 gave answer 5, which is 4+1=5. So is answer always n+1? That would be too trivial? Let's test with some other possible: n=1, s="L": p=0,q=1 => possible sums: either 0 (no command) or -1 (execute L). That's -1 to 0 inclusive? -1,0 => two positions. n+1=2. s="R": p=1,q=0 => positions: 0,1 => 2. So indeed 2. So answer seems to be n+1. But wait, problem constraints: n up to 10^5, trivial answer would be n+1? But maybe there is a twist: the commands are sent in order, and the ignored commands are not "independent"? Actually, the description: "Some commands are sent successfully and some are ignored. If the command is ignored then the position x doesn't change and Mezo simply proceeds to the next command." That is exactly that each command is either executed or not, independently. So indeed any subset works. So answer is n+1. But is that always? Let's think deeper: Could there be any constraints on which subsets are possible? For instance, could there be a scenario where we cannot achieve all sums between -q and p? For example, suppose we have two Ls and one R: s= L L R. Then p=1, q=2 => -2 to 1 inclusive: -2,-1,0,1. Can we achieve -1? Yes: execute one L and no R? That's -1. Or execute two Ls? That's -2. Or execute R only: 1. Or execute L and R: 0? That would be L then R: net 0. Or two Ls and R: -1? Actually two Ls gives -2, plus R gives -1. So all four. So yes.
So answer seems to be n+1. But why is this problem given with n up to 10^5, and example output 5 for 4? Usually such trivial answer would not be asked; maybe I'm missing something. Wait, there might be a nuance: The commands are sent sequentially, and the controller "malfunctions sometimes" meaning that some commands might be ignored, but the controller malfunction might not be independent per command? Usually such problems (like from Codeforces) have a twist: The set of possible final positions can be something like: all integers from -L to R but not necessarily contiguous? But we just argued it's contiguous. Let's double-check with a more exotic scenario: What if the commands are not independent? Are there any constraints like "if a command is ignored, maybe it affects later ones?" No, it just says if command is ignored then position doesn't change and proceed to next. So independent.
Maybe the misunderstanding: Mezo doesn't know which commands will be sent successfully beforehand; he wants to know how many different positions may Zoma end up at. That is exactly number of possible sums of subsets.
But is it true that any subset is possible? In the problem statement, they gave examples: "LRLR" — some possible outcomes: underlined commands are sent successfully. In the first example they underlined the entire string; second, they underlined none; third, they underlined "L" and then "L"? Actually they wrote: "LRLR" — Zoma recieves no commands, doesn't move at all and ends up at position 0 as well; "LRLR" — Zoma moves to the left, then to the left again and ends up in position -2." So they showed that you can choose to execute first and third commands? Actually they said: moves to the left, then to the left again: In "L R L R", left commands are positions 1 and 3? That would be L and L? But both are L? Actually in string LRLR, the L's are at positions 1 and 3; they both are L. So they executed those two L's. So yes, arbitrary subset.
Thus answer is n+1.
But is it always n+1? Let's compute n+1 = number of commands + 1. That matches sample.
Wait, maybe there is a subtlety: The controller malfunctions "sometimes", but maybe the set of commands that are successfully sent is not arbitrary; perhaps there is a constraint that the controller may skip some prefix or something? But the problem says "Some commands are sent successfully and some are ignored." It doesn't specify any restrictions; so it's exactly each command independently either executed or ignored.
Thus the answer is indeed n+1. But why is this problem on a platform? Possibly because it's a trick: The number of distinct positions is simply n+1 regardless of the pattern of L/R. But is it always n+1? Let's check: n=0? Not allowed, n>=1. So n+1 works.
But wait, we need to consider that final position is determined by the count of executed Rs and Ls. The minimum possible sum is - (number of Ls) = -q, maximum is +p. But is it always all integers between -q and p? Yes, as argued. So total distinct = p + q + 1 = n+1.
Thus we could just output n+1. But that seems too easy. However, many Codeforces problems have such simple solutions that are not obvious at first glance; but they typically require some reasoning. Indeed, I recall a Codeforces problem named "Mezo Playing Zoma" or something like that. I think the answer is indeed n+1. Let me search memory: There is Codeforces Round #613 (Div. 2) problem A: "Mezo Playing Zoma"? Actually there is a problem: "Mezo Playing Zoma" maybe from Codeforces Round #???? I think I've seen something like that. The solution is to output n+1. But let's verify with a random example: n=5, s="RRRLL". p=3, q=2 => range -2 to 3 => 6 values = n+1=6. Could we get sum=0? Yes: execute 2 Rs and 2 Ls? That would be 0. Or 3 Rs and 3 Ls? Not possible since only 2 Ls; but 3 Rs and 2 Ls =1, 2 Rs and 2 Ls=0, 1 R and 1 L=0, etc. So 0 is possible. -1: 1 L and 0 R? That's -1, or 2 L and 1 R? = -1? 2-1=1? Actually 2 L (j=2) -> -2; add 1 R -> -1; so possible. All integers appear. So works.
Thus answer is n+1. But wait, is there any scenario where p+q != n? Obviously p+q = n because each command is either L or R. So answer = n+1.
But I recall that in the actual problem, there might be a twist: the commands are sent in real-time, and the malfunction could be such that any prefix of commands could be ignored? Actually, reading the problem statement: "Mezo starts sending n commands to Zoma. ... Some commands are sent successfully and some are ignored. If the command is ignored then the position x doesn't change and Mezo simply proceeds to the next command." That seems independent.
But perhaps there is a nuance: The controller malfunction might cause some commands to be ignored, but the set of commands that are successfully sent could be any subsequence? But any subsequence is exactly any subset (order preserved but that doesn't affect sum). So still fine.
Thus the solution is trivial. However, given that the problem expects reading the string, maybe they want to compute something like the difference between number of L and R? But the answer is just n+1. So we can just print n+1.
But let's double-check with a more subtle test: n=1, s="L": positions possible: 0 or -1 => 2 distinct. n+1=2. Good.
What about n=2, s="LR": p=1,q=1 => possible positions: -1 (only L), 0 (L+R or none), 1 (only R). That's 3, n+1=3. s="LL": p=0,q=2 => positions: -2,-1,0? Actually can we get -1? Yes: execute one L. So -2,-1,0 => 3, n+1=3. s="RR": 0,1,2 => 3.
So indeed all good.
Thus answer: n+1. So we can just read n (ignore string maybe) and output n+1. But caution: is there any possibility that n+1 doesn't hold? Let's attempt to think: Could there be a situation where some integer within range is not achievable due to ordering? For example, to get a certain sum we might need to execute some combination that violates the order? But sum is independent of order, and we can execute any subset because each command is independent. So if we want to achieve sum d, we just select the appropriate Rs and Ls to execute. There's no constraint that the execution order must be consistent with something else. The order is the same as original; executing a subset still respects the order, but the sum is still the sum of selected values. There's no issue.
But wait: there is a potential subtlety: Suppose we want to achieve sum d = 1, and we decide to execute one R and two Ls? That would be -1. Not that. But we choose i Rs and j Ls. The order of these executed commands is the same as they appear in the original string; but does the order affect the final position? No, because addition is commutative. The final position after sequentially applying them is sum of the values. So order doesn't matter.
Thus answer is n+1.
But I recall that the problem "Mezo Playing Zoma" from Codeforces (CF 1285A? Actually I think it's Codeforces Round #615 (Div. 3) problem A? Not sure). Let me search my memory: There is a problem "Mezo Playing Zoma" from Codeforces Round #613 (Div. 2) problem A? Let's think: I recall a problem "A. Mezo Playing Zoma" where the answer is n+1. Yes, that's a known problem. So indeed it's trivial.
Thus solution: read n, read string s (can ignore), print n+1.
But hold on: In the sample input, they gave 4 and LRLR, output 5, which is 4+1=5.
Thus answer is n+1.
But why does the problem include the string? Possibly to distract, or maybe some version of the problem had additional constraints. However, safe to output n+1.
But let's think about if there is any scenario where some positions are unreachable due to the fact that the controller might only malfunction in a certain pattern? But no, the problem statement says "Some commands are sent successfully and some are ignored." It doesn't say "any subset is possible", but it implies that the set of possible outcomes is determined by all possible patterns of successful/ignored commands. Since we don't know which commands will be ignored, we consider all possibilities. So indeed it's all subsets.
Thus answer is n+1.
Therefore we can implement: read integer n, read string s, output n+1.
But wait, there's a nuance: In the problem statement, they say "Mezo starts sending n commands to Zoma. There are two possible commands: L and R." Then they describe the malfunction: "Some commands are sent successfully and some are ignored." It doesn't explicitly say that each command's success is independent, but it's implied that any command may be ignored arbitrarily. Usually in such combinatorial problems, the interpretation is that any subset could be the set of successfully sent commands. So answer is n+1.
Nevertheless, let's double-check: Could there be a scenario where the controller malfunction leads to ignoring of commands in a block, not arbitrary? But the problem doesn't specify any pattern; so we must consider all possibilities. The number of distinct positions is the cardinality of the set of sums over all subsets. That is n+1.
Thus answer.
But perhaps there is a catch: The commands are sent, and the controller might ignore commands based on some unknown distribution, but all subsets are possible. So answer n+1.
Thus we are done.
But wait, what about the time complexity? O(n) to read string but that's fine.
Thus final solution: read n, read s, print n+1.
However, for completeness, I'll also implement a solution that calculates p and q and then outputs p+q+1, but that's the same.
Thus code: int n; string s; cin>>n>>s; cout<<n+1<<endl;
Edge cases: None.
Check: n up to 100000, n+1 fits in int.
Thus final.
But is there any possibility that answer is not n+1? Let's consider if some commands could be ignored in a way that changes the effect? No.
I think it's correct.
But to be absolutely sure, let's test manually with n=3, s="RLR". p=2,q=1 => range -1 to 2 => 4 = n+1=4. Possible positions: -1 (only L), 0 (R+L? Actually if execute R at pos1 and L at pos2? That gives 0. Or just none gives 0), 1 (R only? Actually one R gives 1; also R and R and L? That gives 2-1=1), 2 (two Rs). All present. Good.
Thus solution.
I'll now write final answer. ```python import sys
def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) # The string of commands is in data[1] (if present) but we don't need it. print(n + 1)
if name == "main": main()