CNTINDX - Count The Indexes

no tags 

Let's deal with an array, the most important data structure of computer science. You will be given some operations to do. There will be three types of operations:

Type 1: Insert a number at the end of the array.

Type 2: Delete the last number of the array, where the last number means the latest number which has been inserted.

Type 3: You will get a number and two indices i and j where i<=j. Now you will have to answer how many time the number appears in the array starting from i to j.

You may assume that initially the array is empty.

Input

Each file contains one test case. The first line is an integer Q (1<=Q<=200000), the number of operations. Each of the next Q lines contains an operation. The operations will appear as the formats below:

1 x , where 1<=x<=200000, which means you have to insert number x at the end of the array.

0 , For this operation, you have to delete the last number of the array

2 x i j , Here, you have to find how many times x appears in the array from i to j. Here x will always be present in the array and 1<=i<=j<=length the array.

Output

For deletion, if the array is already empty, then output a string "invalid" (without quote),otherwise you don't need to print anything for deleting numbers. For the operation type of 2, you have to output an integer, how many times x appears in the array from i to j inclusive.

Example

Input:
7
1 10
1 20
2 20 1 2
0
2 10 1 1
0
0 Output: 1
1
invalidĀ 

hide comments
nikita204: 2016-08-27 12:52:33

Getting TLE ?What is the other way to do this question?

topke: 2016-01-29 18:33:02

2 x i j , says that number x is always presented in the array, is not true. I got 2 segmentation faults cause of it. Be careful :-)

Rishav Goyal: 2015-07-14 10:44:21

invalid testcases. in 2nd query, x may not be in array.


Added by:Raihat Zaman Neloy
Date:2014-08-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64