CNTINDX  Count The Indexes
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 & 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 opeation. 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 appers 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:
20160827 12:52:33
Getting TLE ?What is the other way to do this question?


topke:
20160129 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:
20150714 10:44:21
invalid testcases. in 2nd query, x may not be in array. 
Added by:  Raihat Zaman Neloy 
Date:  20140812 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 