题号：NC13819
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
ACM-ICPC有一种称为"Honorable Mention"（荣誉提名）的奖项，在一场有n支队伍的比赛中，这个奖项会颁发给排名>0.6*n的队伍，这里认为排名从1到n，比如n=10，排名>6的队伍会获得荣誉提名。
现在有n支队伍参加比赛，目前第i支队伍的排名是p_i，接下来会发生q个事件，事件分为两种：
1. 给定x,y(1 ≤ x,y ≤ n)，表示第x支队伍的排名上升到y，记原来的排名为t，保证y<t，并且第x支队伍的排名上升后，原来排名为t-1,t-2,...,y+1,y的队伍的排名都会下降一名，
2. 给定x,y(1 ≤ x ≤ y ≤ n)，小Q同学想知道第x到第y支队伍中有多少支队伍会获得荣誉提名。
输入描述:
第一行是一个正整数T(≤ 500)，表示测试数据的组数， 对于每组测试数据， 第一行是一个整数n(1 ≤ n ≤ 50000)，表示参赛队伍数量， 第二行包含n个以空格分隔的整数p_1,p_2,...,p_n，保证是1到n的排列，表示当前每支队伍的排名， 第三行是一个整数q(1 ≤ q ≤ 50000)，表示接下来发生的事件数 接下来q行，每行包含三个整数op(1 ≤ op ≤ 2),x,y，其中op表示事件的类型， 保证满足n>500或q>500的数据不超过10组。
输出描述:
对于每个第2类事件，输出一个整数，表示第x到y支队伍中荣誉提名的队伍数量。
备注:
排名越高当然是数字越小……