- Practice
- Data Structures
- Advanced
- Array and Queries

# Array and Queries

# Array and Queries

Given an array, you are asked to perform a number of queries and divide the array into what are called, *beautiful* subsequences.

The array has length . A function is defined to be a minimal possible , such that it's possible to divide array into *beautiful* subsequences. Note that each element of an array should belong to exactly one subsequence, and subsequence does not necessarily need to be consecutive.

A subsequence with length is called *beautiful* if and only if:

- or
- Let be a sorted version of . It must hold that for every

For instance, if , would be . Because, you can divide into *beautiful* subsequences either like and or like and .

You have to answer queries. Each query is of the type:

- : you need to change a value of to , i.e. . Here is .

After each query, for the value of , lets denote that value as , where indicates the query.

You need to find modulo .

**Input Format**

The first line contains a single integer , representing the length of array .

The next line contains the array given as space-separated integers.

The next line contains a single integer , representing the number of queries.

Each of the lines contain two integers and , which is described above.

**Constraints**

**Output Format**

Print the required answer in one line.

**Sample Input 0**

```
5
2 2 1 1 1
2
3 2
5 5
```

**Sample Output 0**

```
11
```

**Explanation 0**

The initial array is

- After query the array becomes this can be divided into subsequences as , and .
- After query the array becomes this can be divided into subsequences as , , and .

Hence, calculating we get

**Sample Input 1**

```
2
3 3
3
2 4
1 5
2 2
```

**Sample Output 1**

```
9
```

**Explanation 1**

The initial array is

- After query the array becomes this can be divided into subsequence as .
- After query the array becomes this can be divided into subsequence as .
- After query the array becomes this can be divided into subsequences as and .

Hence, calculating we get