Vasya and Robot
Contest: Educational Codeforces Round 53 (Rated for Div. 2)
Difficulty rating: 1800
Tags: binary search, two pointers

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell $$$(0, 0)$$$. Robot can perform the following four kinds of operations:

- U — move from $$$(x, y)$$$ to $$$(x, y + 1)$$$;
- D — move from $$$(x, y)$$$ to $$$(x, y - 1)$$$;
- L — move from $$$(x, y)$$$ to $$$(x - 1, y)$$$;
- R — move from $$$(x, y)$$$ to $$$(x + 1, y)$$$.

Vasya also has got a sequence of $$$n$$$ operations. Vasya wants to modify this sequence so after performing it the robot will end up in $$$(x, y)$$$.

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: $$$maxID - minID + 1$$$, where $$$maxID$$$ is the maximum index of a changed operation, and $$$minID$$$ is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices $$$2$$$, $$$5$$$ and $$$7$$$ are changed, so the length of changed subsegment is $$$7 - 2 + 1 = 6$$$. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is $$$1$$$.

If there are no changes, then the length of changed subsegment is $$$0$$$. Changing an operation means replacing it with some operation (possibly the same); Vasya can't insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from $$$(0, 0)$$$ to $$$(x, y)$$$, or tell him that it's impossible.

Input format:
The first line contains one integer number $$$n~(1 \le n \le 2 \cdot 10^5)$$$ — the number of operations.

The second line contains the sequence of operations — a string of $$$n$$$ characters. Each character is either U, D, L or R.

The third line contains two integers $$$x, y~(-10^9 \le x, y \le 10^9)$$$ — the coordinates of the cell where the robot should end its path.

Output format:
Print one integer — the minimum possible length of subsegment that can be changed so the resulting sequence of operations moves the robot from $$$(0, 0)$$$ to $$$(x, y)$$$. If this change is impossible, print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the sequence can be changed to LULUU. So the length of the changed subsegment is $$$3 - 1 + 1 = 3$$$.

In the second example the given sequence already leads the robot to $$$(x, y)$$$, so the length of the changed subsegment is $$$0$$$.

In the third example the robot can't end his path in the cell $$$(x, y)$$$.

Example input:
5
RURUU
-2 3

Example output:
3

Example input:
4
RULR
1 1

Example output:
0

Editorial:
Denote $$$d = |x| + |y​|$$$. If $$$d > n$$$, then the answer is -1, since the robot will not have the time to reach $$$(x, y)$$$ cell in $$$n$$$ steps. Also, if $$$d$$$ and $$$n$$$ have different parity, then the answer is also -1, as in one move the robot changes the parity of the sum of its coordinates.
In all other cases, the answer exists. Let's use binary search to solve this problem. Consider all segments of length $$$len$$$. For a fixed length of the segment $$$len$$$, let's iterate over the position of the beginning of the segment $$$l$$$. At the same time, we will maintain the cell that the robot will stop at if it execute all commands, except commands with indices $$$l, l + 1, \dots, l + len - 1$$$. We denote this position as $$$(x_0, y_0)$$$. We also calculate the distances from the cell $$$(x_0, y_0)$$$ to the cell $$$(x, y)$$$ — the value $$$d_0 = |x - x_0| + |y ​​- y_0|$$$. If there is at least one position of the beginning of the segment for which $$$d_0 \le len$$$, then we can change the segment of length $$$len$$$ so that the robot comes to the $$$(x, y)$$$ cell, otherwise it can't.