There is an arrangement of clothes in the form of a stack. There are N clothes with you and each cloth has a color Col[i] associated with it.1st cloth is at the bottom and Nth cloth at the top.
Now you have to answer Q queries:
Each query can be of 2 types:
Type-1 query indicated that you place a cloth of color C on top of the stack.
Type 2 query gives you a color C a number K which means you need to pick the Kth cloth from top having color C.If its not possible print -1.If you find the Kth cloth then you take that cloth out of the stack and put all other clothes back in their original order.For type 2 query if you get a cloth then print the number of clothes you had to pop from the stack before you see your desired cloth.
Input Format:
First line contains an integer N containing the initial number of clothes.
Next line contains N space separated integers denoting the colors of the ith Cloth.
Next line contains an integer Q.
Each query has a type (ty) .
For type 1 query you get another integer C.
For type 2 query you get 2 integers C and K.
Output Format
Print the answers for the type 2 queries in new line
Constraints
\(1 \le N,Q \le 5*10^5\)
\(1 \le C,Col[i] \le 10^5 \)
\(1 \le K \le 10^6\)
\(1 \le ty \le 2\)
Initial Arrangement :[1 2 3 1 2 1 3 10 3 2]
Query 1: 3rd cloth of type 2. This is at position 2. So you have to pick 8 clothes.
After query 1 Arrangement:[1 3 1 2 1 3 10 3 2]
Query 2: Only 2 clothes of color 2 is available so answer is -1.
After Query 3: Arrangement:[1 3 1 2 1 3 10 3 2 1]
Query 4: Get 4th cloth of type 1.This is at position 1. So you have to pick 9 clothes.
After query 4 Arrangement:[3 1 2 1 3 10 3 2 1]
Query 5:Get 1st cloth of color 1 . This is at the top of the stack so answer is 0.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor