Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Taju Kage Bunshin No Jutsu

By rohijulislam · Limits 3s, 512 MB

Naruto Uzumaki is one of the strongest ninja of RUET (Rasengan University of Ebisu and Tobi), possessing unnaturally huge amount of chakra (a kind of energy). Due to this, he can create a lot of shadow clones (duplicates of himself) with his Shadow Clone Jutsu. Right now, Naruto is bored so he’s just playing around with his shadow clones.

Naruto has already created $N$ shadow clones and lined them up in a row. The $i$-th clone has $C^i$ amount of chakra in it. Naruto can do the following operations in his whim.

  1. Add $V$: Makes a new shadow clone with V amount of chakra and adds him to the end of the line.
  2. Remove: Destroys the last shadow clone of the line.
  3. Query $L$ $R$ $K$ – Finds the shadow clone with $K$-th largest chakra in $[L, R]$ range i.e. the $K$-th shadow clone if you sort the clones with position between L and R in the line according to their chakra in descending order.

Being a big fan of Naruto, you want to make a video game on Naruto following these 3 operations. In this problem, you have to do exactly that.

Input

The first line contains one integer $N$ ($1 \le N \le 10^5$), the number of shadow clones that has been already created. The next line contains $N$ space separated integers denoting an array $A$ ($1 ≤ A[i] ≤ 10^9$). Then there will be an integer $Q$ ($1 \le Q \le 10^5$) - the number of operation Naruto performs. Then next $Q$ lines contains one of the following types:

  • $\texttt{1 V}$: Add a shadow clone with $V$ ($1 \le V \le 10^9$) amount chakra to the end of the line
  • $\texttt{2}$: Destroys the last shadow clone of the line
  • $\texttt{3 L R K}$: Finds the shadow clone with $K$-th ($1 \le K \le R-L+1$) largest chakra in $[L, R]$ ($1 \le L, R \le \texttt{Total Number of Current Shadow Clones}$) range i.e. the $K$-th shadow clone if you sort the clones with position between $L$ and $R$ in the line according to their chakra in descending order. It is guaranteed that shadow clones will always exist in $[L, R]$ range.

Output

For each 3rd type of operation you have to print a single integer that denotes the $K$-th largest chakra in $[L, R]$ range.

Sample

InputOutput
3
7 3 5 
7
3 1 3 2
1 10
3 1 4 2
2
2
1 1
3 2 3 2
5
7
1

Discussion

Statistics


57% Solution Ratio

YouKnowWhoEarliest, Aug '19

johnwickpencilFastest, 0.2s

emrul_muLightest, 25 MB

omar24Shortest, 1980B

Submit

Login to submit

Editorial

Approach 1: Trie with each node saving all the indices of numbers saved under that node Approach 2:...