记录编号	196169	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.293 s
提交时间	2015-10-20 22:08:44	内存使用	7.73 MiB

/*****************************************************************************/
/******************************Designed By Asm.Def****************************/
/*****************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
#define FREAD
#define FREADLENTH 5000000
#ifdef FREAD
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 100006, INF = 0x7fffffff;
typedef long long LL;
#define upb(x) (upper_bound(seq + 1, seq + 1 + L, x) - seq)
#define lwb(x) (lower_bound(seq + 1, seq + 1 + L, x) - seq)

int N, L, Q, A[maxn], seq[maxn], tmp[maxn], rfst[maxn], lfst[maxn];
LL S[maxn];

inline void init(){
	getd(N), getd(Q);
	int i, t;
	for(i = 1;i <= N;++i)getd(A[i]), tmp[i] = A[i];
	sort(tmp + 1, tmp + N + 1);
	seq[1] = tmp[1];L = 1;
	for(i = 2;i <= N;++i)if(tmp[i] != seq[L])seq[++L] = tmp[i];
	A[0] = A[N + 1] = INF;

	lfst[1] = 0;
	for(i = 2;i <= N;++i){
		t = i - 1;
		while(A[t] < A[i])t = lfst[t];
		lfst[i] = t;
	}

	rfst[N] = N + 1;
	for(i = N - 1;i;--i){
		t = i + 1;
		while(A[t] <= A[i])t = rfst[t];
		rfst[i] = t;
	}

	for(i = 1;i <= N;++i)S[lwb(A[i])] += ((LL)(i - lfst[i])) * ((LL)(rfst[i] - i));

	for(i = 2;i <= L;++i)S[i] += S[i-1];
	S[L + 1] = S[L];
}

inline int getopt(){
	char ch = getc();
	while(ch != '<' && ch != '>' && ch != '=')ch = getc();
	return (ch == '>') ? 0 : (ch == '=' ? 1 : 2);
}

inline void work(){
	int q, K;
	while(Q--){
		q = getopt(), getd(K);
		if(!q)printf("%lld\n", S[L] - S[upb(K)-1]);
		else if(q == 1)printf("%lld\n", S[upb(K)-1] - S[lwb(K)-1]);
		else printf("%lld\n", S[lwb(K)-1]);
	}

}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#else
	SetFile(jxthree);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif
	init();
	work();


#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}