2. 学数数

【题目描述】

从前有一只咩，还有一只叽，还有……嗯……一只毒。

毒是咩和叽的师父。

咩经常算不对像3+0.5这样的数，它总认为3+0.5=5。叽经常算不对60+20这样的数，它总认为60+20=100。

所以毒为了锻炼它们数数的能力，想出了下面这个游戏：

毒先在纸上写下n个数a1，a2，…，an，然后咩和叽会找出所有的连续子数组(共有n*(n+1)/2个)，在自己的纸上记录下每个连续子数组的最大值，那之后毒会给

咩和叽Q个问题，每个问题形如下面三种之一：

1．记录的数中有多少个大于K?

2．记录的数中有多少个等于K?

3．记录的数中有多少个小于K?

然而这只咩太蠢了，总是答错毒的问题，咩很伤心，请你帮帮它吧!

【输入格式】

第一行两个整数n，Q。

第二行n个整数a1，a2，…，an。

下面Q行，每行有一个字符op和一个整数K。

如果op是“>”，说明是第一种问题。

如果op是“=”，说明是第二种问题。

如果op是“<"，说明是第三种问题

【输出格式】

共有Q行，第i行表示第i个问题的答案。

【样例输入】

3  5



1  2  3



>  1



<  2



=  3



>  4



<  5

【样例输出】

5



1



3



0



6

【提示】

 咩和叽的纸上应该写着1，2，2，3，3，3。

  数据范围与约定

 对于20％的数据，1≤n≤200，1≤Q≤200，1≤ai，K≤10^6。

 对于40％的数据，1≤n≤5000，1≤Q≤5000，1≤ai，K≤10^6。

 对于60％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^6，ai两两不同。

 对于80％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^6。

 对于1OO％的数据，1≤n≤10^5，1≤Q≤10^5，1≤ai，K≤10^9。

【来源】

在此键入。