Description

On Jiayuan’s birthday, her friend bought an interesting toy from an online marketplace and gave it to her.

There is a sequence on the toy. The values of some elements in the sequence may change, but at any time at most one value changes. Jiayuan has already figured out all possible changes. She wants to ask you whether it is possible to choose a subsequence that is nondecreasing in the original sequence and under any single change. Please tell her the maximum possible length of such a subsequence.

Input Format

The first line contains two positive integers $n, m$, representing the length of the sequence and the number of changes.

The next line contains $n$ integers, representing the original state of the sequence.

The next $m$ lines each contain $2$ integers $x, y$, meaning the $x$-th element of the sequence can change to the value $y$.

Output Format

Output a single integer, representing the answer.

3 4 
1 2 3 
1 2 
2 3 
2 1 
3 4

3

Hint

Note: In each scenario, at most one value changes.

In the sample input, all changed sequences are:

1 2 3
2 2 3
1 3 3
1 1 3
1 2 4

Choosing the entire original sequence as the subsequence works; it remains nondecreasing under any single change.

For $20\%$ of the testdata, all numbers are positive integers and at most $300$.

For $50\%$ of the testdata, all numbers are positive integers and at most $3000$.

For $100\%$ of the testdata, all numbers are positive integers and at most $10^5$. $1 \le x \le n$.

Translated by ChatGPT 5