[problem:Some Random Problem]

E. Straw Hat's Blue-Red Permutation

Now consider separately two red numbers $$$a_{i}$$$ and $$$a_{j}$$$ such that $$$a_{i} \gt a_{j}$$$ . If $$$x$$$ is produced by increasing $$$a_{i}$$$ and $$$y$$$ is produced by increasing $$$a_{j}$$$ , and in the same time $$$x \lt y$$$ then $$$y \gt x⩾a_{i} \gt a_{j}$$$ , and the following is also true: $$$x \gt a_{j}$$$ and $$$y \gt a_{i}$$$ . So we just showed that if an answer exists, it also exists if greater numbers are produced by greater values from the input. The same holds for the blue numbers.

Let us sort all elements ai by the key $$$(c_{i},a_{i})$$$ , where $$$c_{i}$$$ the color of $$$i-th$$$ element (and blue comes before red). It remains to check that for any $$$t$$$ from $$$1$$$ to $$$n$$$ we can get the number $$$t$$$ from the $$$t$$$ -th element of the obtained sorted array. To do this, we iterate through it and check that either $$$c_{t}='B'$$$ and $$$a_{t}⩾t$$$ so it can be reduced to $$$t$$$, or, symmetrically, $$$c_{t}='R'$$$ and $$$a_{t}⩽t$$$. <\spoiler>