坎通

题目背景

阴霾之下，铃木贞一在思考着坎通的未来。

“dmt，坎通怎么成了这个样子。”

整个坎通就是东亚经济制度改革的试点特区，铃木若渴望变革，必定要先制定好坎通的经济发展计划。

题目描述

铃木希望制定一个 $n$ 年计划。他先确定了一个长度为 $n$ 的序列 $A$，表示计划的制定限制：第 $i$ 年的预期经济增长速度必须是前 $i$ 年中第 $a_i$ 快的。

你需要构造一个长度为 $n$ 的排列 $B$，其中 $b_i$ 表示第 $i$ 年的预期经济增长速度在全部 $n$ 年中的总排名，详见样例。

在动荡的年代，经济计划需要随时变动，所以 $A$ 也会不断变化。但是铃木不想给你的工作增添太大负担，于是他只需要你给出排列中的一项即可。

接下来共有 $q$ 次操作，分为以下两种：

• 操作 1 x y：令 $a_x=y$；
• 操作 2 x：在当前序列 $A$ 的限制下，输出 $b_x$ 的值。如果存在多种合法排列，输出任意一种方案对应的 $b_x$ 即可。数据保证有解。

输入格式

第一行包含一个整数 $n$，表示序列 $A$ 和排列 $B$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示序列 $A$。

第三行包含一个整数 $q$，表示操作数量。

接下来 $q$ 行，每行表示一次操作，格式为以下两种之一：

• 1 x y：令 $a_x=y$；
• 2 x：询问当前限制下的 $b_x$。

输出格式

对于每次操作 2 x，输出一行一个整数，表示一个合法排列中的 $b_x$。

样例 1

输入

2
1 1
5
2 1
2 2
1 2 2
2 1
2 2

输出

2
1
1
2

解释

对于第一次询问，由于 $a_2=1$，即第 $2$ 年必须是前 $2$ 年中发展速度最快的，所以第二年一定排名第一，第一年只能排名第二，因此输出 $2$。

样例 2

输入

5
1 1 3 4 5
9
2 2
2 5
1 2 2
2 2
2 5
1 3 3
1 5 2
2 2
2 5

输出

1
5
2
5
3
2

解释

对于第一次询问，由于 $a_2=1$，即第 $2$ 年必须是前 $2$ 年中发展速度最快的；同时，后三年的每一年 $i$ 都是前 $i$ 年中经济发展速度最慢的，所以第二年就是全部 $5$ 年中发展速度最快的一年，输出 $1$。

下发的样例 $3,4,5,6$ 分别满足子任务 $2,3,4,5$。

数据规模与约定

对于 $100\%$ 的数据：

保证数据对任意操作 2 均有解。

子任务