问题描述 |
---|
有 n 堆积木,初始时每堆积木的数量都为零,涂涂很无聊,于是他重复了 m 次以下操作: 向区间 [L,R] 内的每堆积木中添加一个,即对于 L <= i <= R,a[i] += 1。 这时罗少来了,他给出了一个他认为好看的积木序列,涂涂希望再经过一次上述操作后,每堆积木的数量与罗少给出序列对应位置上的数字尽可能多的相同。 比如涂涂经过 m 次操作完以后积木的数量为:1 1 2 3 2,罗少给出的积木序列为:2 2 3 3 3,那么涂涂可以向区间 [1,3] 内的每堆积木都添加一个使其变成:2 2 3 3 2,如此以来对应位置相同的数量就为 4(第1、2、3、4堆对应相同),当然,涂涂也可以选择向区间 [1,5] 内的每堆积木都添加一个使其变成:2 2 3 4 3,这样对应位置相同的数量也为 4(第1、2、3、5堆对应相同)。 值得注意的是,如果罗少给出的序列与涂涂操作完 m 次以后的积木数量完全一致时,涂涂可以选择放弃最后的操作。 |
输入描述 |
第一行是一个正整数 n 代表积木的堆数。(1 <= n <= 100000) 然后是一个正整数 m 代表涂涂操作的次数。(1 <= m <= 100000) 接下来 m 行,每行包含两个数字代表 L 和 R。(1 <= L <= R <= n) 最后是 n 个整数,代表罗少给出的积木序列。 |
输出描述 |
最多可以有多少堆积木的数量与罗少给出序列对应位置的数字相等,不要换行。 |
样例输入复制样例 |
5 3 1 5 3 5 4 4 2 2 3 3 3 |
样例输出 |
4 |
提示说明 |
样例就是描述中的例子。 |
相关 |