CF788E.New task

On the 228-th international Uzhlyandian Wars strategic game tournament teams from each country are called. The teams should consist of 5 participants.

The team of Uzhlyandia will consist of soldiers, because there are no gamers.

Masha is a new minister of defense and gaming. The prime duty of the minister is to calculate the efficiency of the Uzhlandian army. The army consists of n soldiers standing in a row, enumerated from 1 to n. For each soldier we know his skill in Uzhlyandian Wars: the i-th soldier's skill is a__i.

It was decided that the team will consist of three players and two assistants. The skills of players should be same, and the assistants' skills should not be greater than the players' skill. Moreover, it is important for Masha that one of the assistants should stand in the row to the left of the players, and the other one should stand in the row to the right of the players. Formally, a team is five soldiers with indexes i, j, k, l, p, such that 1 ≤ i < j < k < l < p ≤ n and a__i ≤ a__j = a__k = a__l ≥ a__p.

The efficiency of the army is the number of different teams Masha can choose. Two teams are considered different if there is such i such that the i-th soldier is a member of one team, but not a member of the other team.

Initially, all players are able to be players. For some reasons, sometimes some soldiers become unable to be players. Sometimes some soldiers, that were unable to be players, become able to be players. At any time any soldier is able to be an assistant. Masha wants to control the efficiency of the army, so she asked you to tell her the number of different possible teams modulo 1000000007 (109 + 7) after each change.

在第228届国际乌日兰迪亚战争战略游戏锦标赛中，各国均需派出代表队参赛。每支代表队应由5名队员组成。

乌日兰迪亚代表队将由士兵组成，因为该国没有游戏玩家。

玛莎是新任国防与游戏部长。部长的首要职责是计算乌日兰迪亚军队的效率。军队由排成一列的 $n$ 名士兵组成，编号从 $1$ 到 $n$。对于每名士兵，我们已知其在乌日兰迪亚战争中的技能值：第 $i$ 名士兵的技能值为 $a_i$。

经决定，代表队由三名选手（players）和两名助理（assistants）组成。三名选手的技能值必须相等；而两名助理的技能值均不得大于选手的技能值。此外，玛莎特别强调：其中一名助理必须站在选手队伍的左侧（即在序列中位于所有三名选手之前），另一名助理则必须站在选手队伍的右侧（即在序列中位于所有三名选手之后）。形式化地，一支代表队由五名士兵构成，其下标为 $i, j, k, l, p$，满足 $1 \le i < j < k < l < p \le n$ 且 $a_i \le a_j = a_k = a_l \ge a_p$。

军队的效率即为玛莎可选出的不同代表队的数量。若存在某个下标 $i$，使得第 $i$ 名士兵属于其中一支代表队但不属于另一支，则认为这两支代表队不同。

初始时，所有士兵均可担任选手。但由于某些原因，有时部分士兵会暂时失去担任选手的资格；有时此前失去资格的士兵又恢复了担任选手的资格。在任意时刻，所有士兵均始终可担任助理。玛莎希望实时掌控军队效率，因此她要求你：在每次资格变更后，输出当前可能的不同代表队数量对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains single integer n (1 ≤ n ≤ 105) — the number of soldiers in Uzhlyandia.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the soldiers' skills.

The third line contains single integer m (1 ≤ m ≤ 105) — the number of changes.

The next m lines contain the changes, each change is described with two integers t and x (1 ≤ t ≤ 2, 1 ≤ x ≤ n) on a separate line. If t = 1, then the x-th soldier is unable to be a player after this change. If t = 2, then the x-th soldier is able to be a player after this change.

It is guaranteed that before each query of the first type the soldier is able to be a player, and before each query of the second type the soldier is unable to be a player.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——乌日兰迪亚的士兵人数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——士兵们的技能值。

第三行包含一个整数 $m$（$1 \leq m \leq 10^5$）——修改操作的次数。

接下来的 $m$ 行描述了每次修改操作，每行包含两个整数 $t$ 和 $x$（$1 \leq t \leq 2$，$1 \leq x \leq n$）。若 $t = 1$，则第 $x$ 位士兵在此操作后将无法成为选手；若 $t = 2$，则第 $x$ 位士兵在此操作后将可以成为选手。

保证：每次类型为 $1$ 的查询前，该士兵当前是可以成为选手的；每次类型为 $2$ 的查询前，该士兵当前是不能成为选手的。

Print m integers — the number of distinct teams after each change.

Print the answers modulo 1000000007 (109 + 7).

输出 m 个整数——每次修改后不同队伍的数量。

答案对 1000000007（10⁹ + 7）取模。

In the first example, after the first change the only team consists of soldiers [1, 2, 4, 5, 6]. After the second change any five soldiers can form a team.

In the first example after the first change the only team is soldiers [1, 2, 3, 7, 8]. After the second change the possible teams are: [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]. After the third change the possible teams are: [1, 3, 5, 7, 8], [2, 3, 5, 7, 8].

在第一个例子中，第一次修改后，唯一可能的队伍由士兵 [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]。