SID - Search Insert Delete

You are given a bunch of data (all are positive 32 bit numbers) to operate on. The only operations on the data are search, insert, and delete. When storing the data you have to remember its rank, that is the original position when the data is being inserted. All successful operations must return the ranks of the data. Failed operations should return NONE as the answer.

Your objective is to execute all of the operations as fast as possible.

Input

The first line of input is N and M, separated by a space, N is the number of initial data. (0 <= N < 1000000) and M is the number of operations against the data. (0 <= M < 1000000).

The second line contains N data, separated by blanks. All data are positive 32 bits numbers

The next M lines contains operations against the data. Each line contains a symbol and a number, separated by a space. 

There are 3 symbols (S, I, D), each representing search, insert, and delete operation.

'S number' tries to find the number in the stored data, and outputs its first rank in the stored data (as originally inserted), or NONE if no such number exists.

'I number' inserts the number into the stored data, and outputs its rank in the stored data. (Data can be duplicated).

'D number' deletes the least ranked number found in the stored data, and outputs its rank, or NONE if no such number originally exists.

Output

There is an output for each executed operation. See the above input description about each operation for the detail of the output.

Example

Input:
10 6
20 12 10 28 20 50 49 8 51 1
S 20
I 3
S 11
D 20
I 2
S 20

Output:
1
11
NONE
1
12
5

Added by:Jimmy Tirtawangsa
Date:2012-10-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32-GCC C-CLANG C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL FORTRAN GO GOSU JAVA JULIA KTLN LUA OBJC OBJC-CLANG PAS-GPC PAS-FPC PYTHON PYPY PYPY3 PYTHON3 RUST
Resource:Own problem

hide comments
2020-02-06 05:49:46
Do not decrement rank when deleting, it's the number of insert operations rather than position in stored data like the statement says (contradicting the sample, eg. when I 2 is performed, stored data is of size 10).
2019-07-24 00:02:03 David
Java needs more time.
2016-09-29 13:09:43 Bhumit
Is time limit too hard for Java?
TLE even with fast I/O and HashMap. :/
2016-05-24 23:46:22
It's interesting that unordered_multimap is much faster than unordered_map of (int, queue) even though equal_range() only returns forward iterators. Moreover, unordered_multimap consumes 20x less space.
2015-10-23 07:52:12 mkrjn99
Look out for trailing spaces at the end of line. Caused me numerous WAs

Last edit: 2015-10-23 07:52:37
2015-05-10 22:37:57 Ivan Sandrk
unordered_multimap ftw xD

the test cases need updating, there has to be a test case where all the numbers are the same (so solutions implementing a hash table deteriorate to O(N))
2014-08-23 06:53:56 (Tjandra Satria Gunawan)(曾毅昆)
Finally AC using normal balanced binary search tree (without huge memory hashing and it's faster) ;-)
And I solve this problem using the same technique to solve ORDERSET, the fun is I'm rank#4 on this and that problem :-D
EDIT: I delete some unused debug process on my code, now I'm #3 on this problem.

Last edit: 2014-08-23 07:10:29
2013-09-13 19:00:07 Sumit Kumar
Is the problem with I/O rectified? I'm getting WA not TLE with O(nlogn)!
2013-08-28 23:30:20 (Tjandra Satria Gunawan)(曾毅昆)
Finally AC after a long time :-) Great problem @Jimmy Tirtawangsa
2013-02-11 08:34:49 :D
If you're having problems, try using unsigned 32-bit integers for values.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.