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 Ci amount of chakra in it. Naruto can do the following operations in his whim.
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.
The first line contains one integer N- the number of shadow clones that has been already created. The next line contains N space separated integers denoting an array A. Then there will be an integer Q - the number of operation Naruto performs. Then next Q lines contains one of the following types:
For each 3rd type of operation - you have to print a single integer that denotes the K-th largest chakra in [L, R] range.
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