题目描述

给定一个长度为 $n$ 的序列 $a$ ，以及 $q$ 次操作。操作分为以下两种：

• 操作1：指令形式为 $1\ x\ y$ ，表示将序列中第 $x$ 个数修改为 $y$ 。
• 操作2：指令形式为 $2\ p$ ，表示查询序列中第一个不小于 $p$ 的数的位置。

输入格式

• 第一行输入一个正整数 $n$ ，表示序列的长度。
• 第二行输入 $n$ 个整数，表示序列 $a$ 的元素。
• 第三行输入一个正整数 $q$ ，表示操作的次数。
• 接下来 $q$ 行，对于操作 $1$ ，每行输入三个正整数，分别为操作类型 $op = 1$ 、修改位置 $x$ 以及修改值 $y$ ；对于操作 $2$ ，每行输入两个正整数，分别为操作类型 $op = 2$ 以及需要查询的数 $p$ 。

输出格式

对于每个操作 $2$ ，输出一个整数。若存在第一个不小于查询数 $p$ 的数，则输出其位置；若不存在，则输出 $-1$ 。

输入输出样例

输入

5
5 4 3 9 1
5
2 3
2 10
1 5 10
2 10
2 6

输出

1
-1
5
4

说明

• 对于第一次操作，序列中第一个不小于 $3$ 的数为 $5$ ，其位置为 $1$ ，所以输出 $1$ 。
• 对于第三次操作，由于序列中没有比 $10$ 大的数，故输出 $-1$ 。

数据范围

• 30%的数据：
  • $1 \leq n \leq 1000$
  • $1 \leq a_{i} \leq 1000$
  • $1 \leq q \leq 1000$
  • $1 \leq x \leq n$
  • $1 \leq y, p \leq 1000$
• 60%的数据：
  • $1 \leq n \leq 50000$
  • $1 \leq a_{i} \leq 10^{6}$
  • $1 \leq q \leq 50000$
  • $1 \leq x \leq n$
  • $1 \leq y, p \leq 10^{6}$
• 100%的数据：
  • $1 \leq n \leq 2\times 10^{5}$
  • $1 \leq a_{i} \leq 10^{9}$
  • $1 \leq q \leq 2\times 10^{5}$
  • $1 \leq op \leq 2$
  • $1 \leq x \leq n$
  • $1 \leq y, p \leq 10^{9}$