最大最小差
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

X 爷爷是牛牛国的一个商人,他选择在国内经商。由于牛牛国处于峡谷之中,所以牛牛国的城市排成了一列,这导致了牛牛国的两端相距太远而且交通不十分便利。 X 爷爷只会在某个范围内进行经商,每次经商,他会选择一件物品,并找到他的活动范围内该物品市面价格差最大的两个城市,从低价的城市买并卖到高价的城市。当然,如果他的活动范围内该物品的价格都一样,不存在额差,那么X爷爷就只能 0 利润空手而归了。

牛牛国女皇牛妹调查了 X 爷爷最近次的经商活动,得到了 X 爷爷的每一次经商活动中物品的单件利润以及所经商的物品当时在所有城市的市面价值,他想知道 X 爷爷有多少种满足的活动范围。 

输入描述:

输入数据第一行两个正整数  ,表示 牛牛国城市数量以及牛妹调查的经商活动数量。 
接下来一行 个自然数,第 个数表示调查的第 次经商活动物品的单件利润。
接下来 行,每行 个正整数,第 行第 列正整数表示第 次经商活动的物品在第 个城市中的市面价值。

对于所有数据,市面价值与利润均不超过

输出描述:

输出一行一个自然数,表示 X 爷爷可能的活动范围数量。
示例1

输入

复制
5 1
2
2 3 1 4 5

输出

复制
2

说明

满足条件的活动范围有 \ [1,3]\ [2,3],X 爷爷在这个活动范围内会从第三座城市买来物品,卖到第二座城市去,单个物品利润为 \text 2