New task
Contest: Codeforces Round 407 (Div. 1)
Difficulty rating: 2900
Tags: data structures

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 ai.

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 ai ≤ aj = ak = al ≥ ap.

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 format:
The first line contains single integer n (1 ≤ n ≤ 105) — the number of soldiers in Uzhlyandia.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 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 format:
Print m integers — the number of distinct teams after each change.

Print the answers modulo 1000000007 (109 + 7).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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].

Example input:
6
1 1 1 1 1 1
2
1 3
2 3

Example output:
1
6

Example input:
8
3 4 4 2 4 5 4 1
3
1 5
2 5
1 2

Example output:
1
6
2

Editorial:
To begin with, we apply scaling to all numbers and replace each element of the array with its position in the sorted array.
Count the answer for the original array. For each i, calculate smaller_prefi as the quantity of such j that j < i, aj ≤ ai and smaller_sufi — the number of such j that j > i, aj ≤ ai. This can be done with a segment tree or a Fenwick tree. If we consider each element as k from the command [i, j, k, l, p], then the answer for fives with this k is $$(\sum_{j=1}^{k-1})$$smaller_prefj, aj = ak)·$$(\sum_{j=k+1}^{n})$$smaller_sufj, aj = ak). The common answer is the sum of the answers for each possible k. Now after each request we will update the answer. We will support for each type of number for the prefix and suffix for 2 segment tree. Since when, an element turns on/off it is important to know only information about elements with the same value, then you can update the answer using only it. Consider array b as a number vector of occurrences of the form au.
In the first "suffix tree" in the sheet we store smaller_sufbi, if the element with the number bi is included, otherwise 0, and in the remaining vertices the sum in the sons. In the second suffix tree we store in the sheet smaller_sufbi·((the number j, such that aj = abi,  < b[i], element with the number j — is included) + 1), if the element with the number bi is included, otherwise 0, and in the remaining vertices the sum in the sons.
For the prefix, you need to do exactly the same thing.
Let cntau be the number of numbers of the form au.
Now when the request for turning off/on the element with number u came, we need to subtract/add to the answer the number of such pentads [i, j, k, l, p] where u = k, u = j, u = l. Further cu =  ((the quantity j, j < u, aj = au) + 1). In other words, cu — is the number in the occurrence vector of numbers of the form au). First, consider the number of fives where u = k. Them is (the sum on the interval [1;cu-1] in the first prefix tree) · (the sum on the segment [cu+1;cntau] in the first "suffix tree").
The number of fives where u = j is ((the sum on the segment [cu+2;cntau] in the second "suffix tree" segments) - ((the number of elements j, j ≤ u, aj = au, the element with the number j is included) +1)· (the sum on the segment [cu+2;cntau] in the first "suffix tree" segments ))·smaller_prefu. The number of fives where u = l must be calculated in the same way as for u = j, only in the other direction.
Updating the values ​​of the suffix tree elements:
• When the item is turned off, you need:   Take the sum on the segment [cu+1;cntau] in the second segment tree in the same segment in the first tree.  Assign the element with the number cu to the element in the second segments tree 0.  Assign the element with the number cu in the first tree 0.
• Take the sum on the segment [cu+1;cntau] in the second segment tree in the same segment in the first tree.
• Assign the element with the number cu to the element in the second segments tree 0.
• Assign the element with the number cu in the first tree 0.
• When you enable an item, you need:   Add on the segment [cu+1;cntau] in the second segment tree the sum on the same line in the first tree.  Assign the element with the number cu in the second tree (the number of such j, j ≤ u, aj = au, the element j is included) + 1)·smaller_suffu.  Assign the element with the number cu in the first tree smaller_sufu.
• Add on the segment [cu+1;cntau] in the second segment tree the sum on the same line in the first tree.
• Assign the element with the number cu in the second tree (the number of such j, j ≤ u, aj = au, the element j is included) + 1)·smaller_suffu.
• Assign the element with the number cu in the first tree smaller_sufu.
The update in the tree with the prefix is the same.
Adding on the segment will be done by a kind of lazy pushing — in the second segment tree you need to have access to the corresponding vertex of the first tree, when changing the vertex, add/subtract the sum at the top of the first segment tree.
The complexity of the solution is O(N·logN + M·logN)) by time, O(N) by memory.