← 返回题目列表

Codeforces · 788/E

E. 新任务

中文机器翻译题面 查看原题

第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]。