Codeforces 1066 C（思維）

傳送門：

題面：

C. Books Queries

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have got a shelf and want to put some books on it.

You are given?qq?queries of three types:

1. L?idid?— put a book having index?idid?on the shelf to the left from the leftmost existing book;
2. R?idid?— put a book having index?idid?on the shelf to the right from the rightmost existing book;
3. ??idid?— calculate the minimum number of books you need to pop from the left or from the right in such a way that the book with index?idid?will be leftmost or rightmost.

You can assume that the first book you will put can have any position (it does not matter) and queries of type?33?are always valid (it is guaranteed that the book in each such query is already placed). You can also assume that you don't put the same book on the shelf twice, so?idids don't repeat in queries of first two types.

Your problem is to answer all the queries of type?33?in order they appear in the input.

Note that after answering the query of type?33?all the books remain on the shelf and the relative order of books does not change.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains one integer?qq?(1≤q≤2?1051≤q≤2?105) — the number of queries.

Then?qq?lines follow. The?ii-th line contains the?ii-th query in format as in the problem statement. It is guaranteed that queries are always valid (for query type?33, it is guaranteed that the book in each such query is already placed, and for other types, it is guaranteed that the book was not placed before).

It is guaranteed that there is at least one query of type?33?in the input.

In each query the constraint?1≤id≤2?1051≤id≤2?105?is met.

Output

Print answers to queries of the type?33?in order they appear in the input.

Examples

input

Copy

8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1

output

Copy

1
1
2

input

Copy

10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115

output

Copy

0
2
1

Note

Let's take a look at the first example and let's consider queries:

1. The shelf will look like?[1][1];
2. The shelf will look like?[1,2][1,2];
3. The shelf will look like?[1,2,3][1,2,3];
4. The shelf looks like?[1,2,3][1,2,3]?so the answer is?11;
5. The shelf will look like?[4,1,2,3][4,1,2,3];
6. The shelf looks like?[4,1,2,3][4,1,2,3]?so the answer is?11;
7. The shelf will look like?[5,4,1,2,3][5,4,1,2,3];
8. The shelf looks like?[5,4,1,2,3][5,4,1,2,3]?so the answer is?22.

Let's take a look at the second example and let's consider queries:

1. The shelf will look like?[100][100];
2. The shelf will look like?[100,100000][100,100000];
3. The shelf will look like?[100,100000,123][100,100000,123];
4. The shelf will look like?[101,100,100000,123][101,100,100000,123];
5. The shelf looks like?[101,100,100000,123][101,100,100000,123]?so the answer is?00;
6. The shelf will look like?[10,101,100,100000,123][10,101,100,100000,123];
7. The shelf will look like?[10,101,100,100000,123,115][10,101,100,100000,123,115];
8. The shelf looks like?[10,101,100,100000,123,115][10,101,100,100000,123,115]?so the answer is?22;
9. The shelf will look like?[10,101,100,100000,123,115,110][10,101,100,100000,123,115,110];
10. The shelf looks like?[10,101,100,100000,123,115,110][10,101,100,100000,123,115,110]?so the answer is?11.

題意：

? ? 有三種操作：（1）‘L’，num，將num放入最左端（2）‘R’，num，（3）‘？’，num，讓你從求出最小從左邊或右邊去除多少個數才能取得數num。

題目分析：

? ? 最開始想得特別復雜，認為需要模擬一個動態向兩邊拓展的數組，并在每一次操作（1）（2）后用線段樹對現在的整個區間的[L,R]+1，最后用map記錄一下最小的在哪里就好了。

? ? 但是看到一堆人過了這個題后才意識到，題目顯然沒有這么復雜！！！不知道為什么會想到用所謂的線段樹

? ??考慮到要用最小的代價將物品取出，故對于某一個物品，必定是在“？”詢問前的最后一次放入的才是最優位置。因此我們只需要用數組對每個數記錄一下最優解，最后分別用取（最優位置-最左端位置，以及最右端-最優位置）中的最小值即可。

代碼：

#include <bits/stdc++.h>
#define maxn 400005
using namespace std;
int a[maxn];
char str[2];
int main()
{int t;scanf("%d",&t);int l=200000;int r=l-1;while(t--){int num;scanf("%s",str);scanf("%d",&num);if(str[0]=='L'){l--;a[num]=l;}else if(str[0]=='R'){r++;a[num]=r;}else{int res=min(a[num]-l,r-a[num]);cout<<res<<endl;}}return 0;
}

?