描述

ZLY有N条船，排成一列
每条船有价值V_i
ZLY会训练一些船只使之价值up
ZLY不时想知道某条船的价值
所以请你帮忙
ZLY答应事成之后给你\(1234567890^0\)-1条船

输入

第一行一个数N
第二行N个正整数V_1、V_2、...、V_N
第三行一个数M
接下来M行
每行二或三个正整数O、A、(B)
若O==1则存在B，表示前A条船受到训练，各船价值对B取max
若O==0则不存在B，表示询问第A条船只价值

对于每个询问，输出一行一个整数，为询问的船只价值

3
2

20% N,M<=10
40% N<=10000 M<=1000
80% N<=\(10^6\),M<=100000
100% 1<=N<=\(10^7\) 1<=M<=\(10^5\) 1<=A<=N 1<=V_i<=\(10^8\) 1<=B<=\(10^8\)

1000ms
128M