English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
Print _m_ integers — the number of distinct teams after each change.
Print the answers modulo 1000000007 (109 + 7).
[samples]
## Note
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\].
在第228届国际Uzhlyandian战争战略游戏锦标赛中，每个国家都派出队伍参赛。队伍必须由#cf_span[5]名成员组成。
Uzhlyandia的队伍将由士兵组成，因为没有游戏玩家。
Masha是新任国防与游戏部长。部长的首要职责是计算Uzhlyandia军队的效率。军队由#cf_span[n]名士兵排成一行组成，编号从#cf_span[1]到#cf_span[n]。对于每名士兵，我们知道他在Uzhlyandian战争中的_技能值_：第#cf_span[i]名士兵的技能值为#cf_span[ai]。
决定队伍由三名玩家和两名助手组成。玩家的技能值必须相同，而助手的技能值不得超过玩家的技能值。此外，Masha要求一名助手必须站在玩家序列的左侧，另一名助手必须站在玩家序列的右侧。形式上，一个队伍由五名士兵组成，其下标为#cf_span[i], #cf_span[j], #cf_span[k], #cf_span[l], #cf_span[p]，满足#cf_span[1 ≤ i < j < k < l < p ≤ n]，且#cf_span[ai ≤ aj = ak = al ≥ ap]。
军队的效率是Masha能选出的不同队伍的数量。两个队伍被认为是不同的，如果存在某个#cf_span[i]，使得第#cf_span[i]名士兵属于其中一个队伍但不属于另一个队伍。
最初，所有士兵都可以作为玩家。由于某些原因，有时某些士兵会失去作为玩家的资格；有时，原本不能作为玩家的士兵又恢复了资格。任何时候，任何士兵都可以作为助手。Masha希望监控军队的效率，因此她要求你在每次变化后告诉她不同可能队伍的数量，结果对#cf_span[1000000007]（#cf_span[109 + 7]）取模。
第一行包含一个整数#cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Uzhlyandia的士兵数量。
第二行包含#cf_span[n]个整数#cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——士兵的技能值。
第三行包含一个整数#cf_span[m]（#cf_span[1 ≤ m ≤ 105]）——变化的次数。
接下来的#cf_span[m]行每行包含两个整数#cf_span[t]和#cf_span[x]（#cf_span[1 ≤ t ≤ 2]，#cf_span[1 ≤ x ≤ n]），描述一次变化。如果#cf_span[t = 1]，则第#cf_span[x]名士兵在此变化后失去作为玩家的资格；如果#cf_span[t = 2]，则第#cf_span[x]名士兵在此变化后恢复作为玩家的资格。
保证在每次第一类查询前，该士兵当前可以作为玩家；在每次第二类查询前，该士兵当前不能作为玩家。
请输出#cf_span[m]个整数——每次变化后不同队伍的数量。
答案对#cf_span[1000000007]（#cf_span[109 + 7]）取模。
在第一个例子中，第一次变化后，唯一的队伍由士兵#cf_span[[1, 2, 4, 5, 6]]组成。第二次变化后，任意五名士兵都可以组成一个队伍。
在第一个例子中，第一次变化后，唯一的队伍是士兵#cf_span[[1, 2, 3, 7, 8]]。第二次变化后，可能的队伍有：#cf_span[[1, 2, 3, 5, 7]]，#cf_span[[1, 2, 3, 5, 8]]，#cf_span[[1, 2, 3, 7, 8]]，#cf_span[[1, 2, 5, 7, 8]]，#cf_span[[1, 3, 5, 7, 8]]，#cf_span[[2, 3, 5, 7, 8]]。第三次变化后，可能的队伍是：#cf_span[[1, 3, 5, 7, 8]]，#cf_span[[2, 3, 5, 7, 8]]。
## Input
第一行包含一个整数#cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Uzhlyandia的士兵数量。第二行包含#cf_span[n]个整数#cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——士兵的技能值。第三行包含一个整数#cf_span[m]（#cf_span[1 ≤ m ≤ 105]）——变化的次数。接下来的#cf_span[m]行每行包含两个整数#cf_span[t]和#cf_span[x]（#cf_span[1 ≤ t ≤ 2]，#cf_span[1 ≤ x ≤ n]），描述一次变化。如果#cf_span[t = 1]，则第#cf_span[x]名士兵在此变化后失去作为玩家的资格；如果#cf_span[t = 2]，则第#cf_span[x]名士兵在此变化后恢复作为玩家的资格。保证在每次第一类查询前，该士兵当前可以作为玩家；在每次第二类查询前，该士兵当前不能作为玩家。
## Output
请输出#cf_span[m]个整数——每次变化后不同队伍的数量。答案对#cf_span[1000000007]（#cf_span[109 + 7]）取模。
[samples]
## Note
在第一个例子中，第一次变化后，唯一的队伍由士兵#cf_span[[1, 2, 4, 5, 6]]组成。第二次变化后，任意五名士兵都可以组成一个队伍。在第一个例子中，第一次变化后，唯一的队伍是士兵#cf_span[[1, 2, 3, 7, 8]]。第二次变化后，可能的队伍有：#cf_span[[1, 2, 3, 5, 7]]，#cf_span[[1, 2, 3, 5, 8]]，#cf_span[[1, 2, 3, 7, 8]]，#cf_span[[1, 2, 5, 7, 8]]，#cf_span[[1, 3, 5, 7, 8]]，#cf_span[[2, 3, 5, 7, 8]]。第三次变化后，可能的队伍是：#cf_span[[1, 3, 5, 7, 8]]，#cf_span[[2, 3, 5, 7, 8]]。
Let $ n $ be the number of soldiers, $ a = [a_1, a_2, \dots, a_n] $ be their skill values, and $ m $ be the number of updates.
Define a binary state array $ p \in \{0,1\}^n $, where $ p_i = 1 $ if soldier $ i $ is **able to be a player**, and $ p_i = 0 $ otherwise. Initially, $ p_i = 1 $ for all $ i $.
A valid team is a 5-tuple of indices $ (i, j, k, l, r) $ such that:
- $ 1 \le i < j < k < l < r \le n $,
- $ a_j = a_k = a_l $ (the three players have equal skill),
- $ a_i \le a_j $ and $ a_r \le a_j $ (the two assistants have skill ≤ player skill),
- $ p_j = p_k = p_l = 1 $ (the three players are eligible),
- $ p_i = 1 $ and $ p_r = 1 $ are **not required** (assistants can always be chosen, regardless of player eligibility).
Let $ S $ be the set of all valid 5-tuples satisfying the above.
The efficiency is $ |S| \mod 1000000007 $.
We are to support $ m $ updates: for each update $ (t, x) $,
- if $ t = 1 $: set $ p_x \leftarrow 0 $,
- if $ t = 2 $: set $ p_x \leftarrow 1 $,
and after each update, output $ |S| \mod 1000000007 $.
---
**Formal Objective:**
Compute, after each update, the number of 5-tuples $ (i, j, k, l, r) $ satisfying:
$$
\begin{cases}
1 \le i < j < k < l < r \le n \\
a_j = a_k = a_l \\
a_i \le a_j \\
a_r \le a_j \\
p_j = p_k = p_l = 1 \\
\end{cases}
$$
Note: $ i $ and $ r $ may be any soldiers (eligible or not) as long as their indices satisfy the order and skill constraints — **only the three central soldiers (players) must be eligible**.
---
**Key Insight:**
Fix a triple of indices $ (j, k, l) $ such that $ j < k < l $ and $ a_j = a_k = a_l $, and $ p_j = p_k = p_l = 1 $. Let $ s = a_j $.
Then, the number of valid choices for the left assistant $ i $ is the number of indices $ i < j $ such that $ a_i \le s $.
Similarly, the number of valid choices for the right assistant $ r $ is the number of indices $ r > l $ such that $ a_r \le s $.
Thus, for each valid player triple $ (j,k,l) $, the number of teams it contributes is:
$$
L(j, s) \cdot R(l, s)
$$
where:
- $ L(j, s) = |\{ i \in [1, j-1] : a_i \le s \}| $
- $ R(l, s) = |\{ r \in [l+1, n] : a_r \le s \}| $
Then the total number of teams is:
$$
\sum_{\substack{1 \le j < k < l \le n \\ a_j = a_k = a_l \\ p_j = p_k = p_l = 1}} L(j, a_j) \cdot R(l, a_j)
$$
We maintain this sum dynamically under updates to $ p $.
---
**Final Formal Statement:**
Let $ \mathcal{T} = \{ (j, k, l) \in [n]^3 : j < k < l, a_j = a_k = a_l \} $
Let $ \mathcal{P} = \{ i \in [n] : p_i = 1 \} $
Define for each $ (j, k, l) \in \mathcal{T} $:
$$
w(j, l, s) = L(j, s) \cdot R(l, s), \quad \text{where } s = a_j
$$
Then the efficiency is:
$$
\sum_{\substack{(j,k,l) \in \mathcal{T} \\ j,k,l \in \mathcal{P}}} w(j, l, a_j)
$$
We are to maintain this sum under point updates to $ p_i \in \{0,1\} $, and output the result modulo $ 10^9 + 7 $ after each update.