第228届国际乌兹利亚战争战略游戏锦标赛上,来自各个国家的队伍被召集。团队应由 5 名参与者组成。
Uzhlyandia 的队伍将由士兵组成,因为没有玩家。
玛莎是新任国防部长和游戏部长。部长的首要职责是计算乌兹兰军队的效率。军队由n名士兵组成,排成一排,从1到n编号。对于每个士兵,我们都知道他在乌兹利亚战争中的技能:第 i 个士兵的技能是 ai。
决定球队将由三名球员和两名助理组成。球员的技术水平应该相同,并且助手的技术水平不能高于球员的水平。此外,对于玛莎来说,重要的是其中一名助手应站在球员左侧的一排,另一名助理应站在球员右侧的一排。形式上,一个团队由 5 名士兵组成,索引为 i、j、k、l、p,满足 1 ≤ i < j < k < l < p ≤ n 且 ai ≤ aj = ak = al ≥ ap。
军队的效率是玛莎可以选择的不同队伍的数量。如果存在这样的 i 使得第 i 个士兵是一个团队的成员,但不是另一个团队的成员,则认为两个团队是不同的。
最初,所有玩家都可以成为玩家。由于某些原因,有时有些士兵无法成为玩家。有时,一些无法成为玩家的士兵能够成为玩家。任何时候任何士兵都可以成为助手。玛莎想要控制军队的效率,所以她要求你告诉她每次改变后不同的可能队伍的数量模1000000007(109 + 7)。
输入
第一行包含单个整数 n (1 ≤ n ≤ 105) — 乌日扬迪亚的士兵数量。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) – 士兵的技能。
第三行包含单个整数 m (1 ≤ m ≤ 105) — 变化次数。
接下来的 m 行包含更改,每个更改在单独的行上用两个整数 t 和 x (1 ≤ t ≤ 2, 1 ≤ x ≤ n) 描述。如果 t = 1,则第 x 个士兵在此更改后无法成为玩家。如果 t = 2,则第 x 个士兵在此更改后可以成为玩家。
保证在每次第一类型查询之前,士兵能够成为玩家,并且在每次第二类型查询之前,士兵不能成为玩家。
输出
打印 m 个整数 — 每次更改后不同团队的数量。
打印以 1000000007 (109 + 7) 为模的答案。
示例
输入 #1
6 1 1 1 1 1 1 2 1 3 2 3
输出 #1
1 6
输入 #2
8 3 4 4 2 4 5 4 1 3 1 5 2 5 1 2
输出 #2
1 6 2
注意
在第一个示例中,第一次更改后,唯一的团队由士兵组成 [1, 2, 4, 5, 6]。第二次变更后,任意五名士兵即可组队。
在第一次更改后的第一个示例中,唯一的团队是士兵 [1, 2, 3, 7, 8]。第二次更改后,可能的球队为:[1, 2, 3, 5, 7],[1, 2, 3, 5, 8],[1, 2, 3, 7, 8],[1, 2, 5, 7, 8],[1, 3, 5, 7, 8],[2, 3, 5, 7, 8]。第三次更改后,可能的球队为:[1,3,5,7,8],[2,3,5,7,8]。