Entrée
La première ligne contient la taille $N$ de la séquence ($2 \le N \le 100{,}000$).
La deuxième ligne contient $A_1, A_2, \ldots, A_N$ ($-100{,}000 \le A_i \le 100{,}000$).
La troisième ligne contient le nombre $M$ de requêtes ($1 \le M \le 100{,}000$).
Les $M$ lignes suivantes contiennent les requêtes.
Toutes les entrées sont des entiers.
Sortie
Pour chaque requête de type $2$, afficher la réponse sur une ligne séparée.
Exemples
Entrée 1
5 1 2 3 4 5 4 2 1 5 1 3 4 1 1 2 1 5 2 3 5
Sortie 1
5 3 2