Cake Eating Simulation

Leopold and Molly both love cakes and have different tastes: Leopold loves to eat cakes while Molly enjoys watching him eat. There are n cakes arranged in a row numbered from 1 to n from left to right, and each cake has a deliciousness value \(d_i\). Initially, Leopold eats a specified cake with index \(a\), leaving that position empty. Then, in every subsequent step, he chooses the cake adjacent to the current contiguous empty block (formed by eaten cakes) that has the smaller deliciousness value (he saves the tastier ones for later).

Occasionally, Molly decorates a cake that has not yet been eaten. When she does so on a cake at index \(x\), its deliciousness is increased so that after decoration, its deliciousness becomes among the top 10 largest values among all remaining cakes. You may assume that at any moment, all uneaten cakes have distinct deliciousness values. Meanwhile, Molly sometimes wonders, for a given cake with index \(b\), how many cakes Leopold will have already eaten before he eats cake \(b\) (i.e. the number of cakes eaten preceding cake \(b\)).

Your task is to process a sequence of operations and answer Molly's queries.

Process Description

Initially, only cake \(a\) is eaten. Let the current contiguous empty block range be \([L, R]\) (initially \(L=R=a\)). At each step, if \(L>1\) then cake \(L-1\) is a candidate, and if \(R<n\) then cake \(R+1\) is a candidate. Leopold chooses the candidate with the smaller deliciousness value \(d_i\) and eats it, updating the empty block accordingly (if the left candidate is eaten then \(L\) becomes \(L-1\), otherwise if the right candidate is eaten then \(R\) becomes \(R+1\)).

Operations

• D x: Molly decorates cake \(x\) (if it is uneaten) by setting its deliciousness to a new value \(d_x = \text{current_max}+1\), where \(\text{current_max}\) is the maximum deliciousness among all cakes (eaten or not) up to that moment.
• Q b: Query how many cakes are eaten before cake \(b\) is eaten. If cake \(b\) has already been eaten, output the number of cakes eaten prior to it.

It is guaranteed that each cake gets a unique deliciousness at all times.

inputFormat

The input begins with a line containing three integers \(n\), \(m\) and \(a\) \( (1 \leq a \leq n)\) where \(n\) is the number of cakes and \(m\) is the number of operations.

The next line contains \(n\) distinct integers \(d_1, d_2, \ldots, d_n\) representing the deliciousness of each cake.

The following \(m\) lines each contain an operation in one of the following two formats:

• D x - Molly decorates cake at position \(x\) (if it is uneaten).
• Q b - Query the number of cakes eaten before cake \(b\) is eaten.

outputFormat

For each query operation, output a single integer on a new line, representing the number of cakes eaten before the queried cake is eaten.

sample

5 3 3
5 1 3 2 4
Q 1
D 4
Q 5

4
3

</p>