Beautiful Sequence Rearrangement

You are given a sequence \(a\) of length \(n\). The commander considers the sequence may not be beautiful enough and wants to rearrange it into \(a'\) in order to make it beautiful.

A sequence \(a\) of length \(n\) is called beautiful if and only if there exists an index \(i\) (\(1 \le i \le n\)) such that:

• For every \(j \in [1, i-1]\), \(a_j > a_{j+1}\). (The prefix is strictly decreasing.)
• For every \(j \in [i+1, n]\), \(a_j > a_{j-1}\). (The suffix is strictly increasing.)

In other words, the sequence has a "V-shape" where the pivot element \(a_i\) is the minimum, with the part before \(i\) strictly decreasing and the part after \(i\) strictly increasing. Note that if \(i=1\) the whole sequence is strictly increasing and if \(i=n\) the whole sequence is strictly decreasing.

The task is to determine how many different rearrangements \(a'\) (i.e. permutations of \(a\)) can yield a beautiful sequence. Because the answer might be extremely large, you are to output the answer modulo \(p\).

However, a fixed sequence \(a\) is too boring. Therefore, you will be given \(m\) modifications. Each modification is given as two integers \(x\) and \(k\) indicating that \(a_x\) should be updated to \(k\). After each modification, you must output the current answer modulo \(p\>.

Note: For a beautiful sequence, observe that if the sequence contains any duplicate numbers then it is impossible to have strict inequalities. Thus, only when all elements in \(a\) are distinct can a beautiful permutation exist. In particular, if all elements are distinct, then the minimum element must appear at the pivot and the remaining \(n-1\) elements can be split arbitrarily into two groups (one for the left of the pivot and one for the right). The left group must be arranged in strictly decreasing (unique) order and the right group in strictly increasing order. Hence, the number of beautiful rearrangements is \(2^{n-1}\) when all elements are distinct, and \(0\) otherwise.

inputFormat

The first line contains three integers \(n\), \(m\), and \(p\) where \(n\) is the length of the sequence, \(m\) is the number of modifications, and \(p\) is the modulus.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial sequence.

Each of the next \(m\) lines contains a modification in the format "x k", meaning that the value at position \(x\) (1-indexed) is updated to \(k\).

outputFormat

After each modification, print a single line containing one integer: the number of beautiful rearrangements of the current sequence \(a\) modulo \(p\).

sample

3 3 1000
2 3 1
1 2
2 2
3 1

4
0
0