题目描述

小铭正在维护一条由 $n$ 个监测点组成的记录序列，第 $i$ 个监测点当前的读数为 $a_i$。

系统在运行过程中可能受到一次短暂扰动。每次扰动只会影响一个位置：某个位置 $x$ 的读数可能临时变为 $y$。小铭已经提前收集到了所有可能出现的扰动情况。

也就是说，系统最终可能处于以下任意一种状态：

• 没有发生扰动，序列保持原样；
• 从给出的 $m$ 种扰动中选择一种发生，并且只有该扰动对应的位置发生变化。

小铭想在扰动发生之前，从原序列中选出若干个位置，组成一个子序列。要求无论系统保持原样，还是发生任意一种给定扰动，这些被选中位置上的数值都必须构成一个不降序列。

请你求出满足条件的子序列的最大长度。

输入格式

第 $1$ 行包含两个正整数 $n,m$，分别表示序列长度和可能扰动的数量。

第 $2$ 行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示序列的初始状态。

接下来 $m$ 行，每行包含两个正整数 $x,y$，表示第 $x$ 个位置的数值可能在某一次扰动中变为 $y$。

输出格式

输出一行一个整数，表示在所有可能状态下都保持不降的子序列的最大长度。

样例

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

3

样例说明

在样例中，系统可能出现的序列为：

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

选择全部 $3$ 个位置时，在以上所有状态中得到的子序列都不降，因此答案为 $3$。

数据范围

• 对于 $20$ 的数据：所有数均为正整数，且不超过 $300$。
• 对于 $50$ 的数据：所有数均为正整数，且不超过 $3000$。
• 对于 $100$ 的数据：所有数均为正整数，且不超过 $10^5$，$1 \le x \le n$。