记录编号	205192	评测结果	AAAAAAAAAA
题目名称	学数数	最终得分	100
用户昵称	slongle	是否通过	通过
代码语言	Pascal	运行时间	1.324 s
提交时间	2015-11-04 21:31:59	内存使用	4.36 MiB

const
 maxn=100050;
var
 t,l,r,x,z:array[0..maxn]of longint;
 sum,y,ans:array[0..maxn]of int64;
 i,j,k:longint;
 n,q,len,tt,ll,rr,mid,pp:longint;
 ch:char;
procedure sort(l,r:longint);
var i,j,a,b:longint; c:int64;
begin
 i:=l; j:=r; a:=x[(l+r) div 2];
 repeat
  while x[i]<a do inc(i);
  while a<x[j] do dec(j);
  if not(i>j) then
   begin
    b:=x[i]; x[i]:=x[j]; x[j]:=b;
    c:=y[i]; y[i]:=y[j]; y[j]:=c;
    inc(i); dec(j);
   end;
 until i>j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;

begin
 assign(input,'jxthree.in'); assign(output,'jxthree.out'); reset(input); rewrite(output);
 readln(n,q);
 for i:=1 to n do
  read(x[i]);
 readln;
 t[1]:=1; l[1]:=1; len:=1; t[0]:=0; x[0]:=maxlongint;
 for i:=2 to n do
  begin
   tt:=0;
   for j:=len downto 0 do
    if x[i]<x[t[j]]
    then begin l[i]:=i-t[j]; tt:=j; break; end
    else r[t[j]]:=i-t[j];
   len:=tt+1; t[len]:=i;
  end;
 for i:=1 to len do
  r[t[i]]:=n+1-t[i];
 for i:=1 to n do
  y[i]:=int64(l[i])*int64(r[i]);
 sort(1,n); len:=0; x[0]:=-1;
 for i:=1 to n do
  if x[i]<>x[i-1] then begin inc(len); z[len]:=x[i]; end;
 tt:=0;
 for i:=1 to n do
  begin
   if x[i]<>x[i-1] then inc(tt);
   inc(ans[tt],y[i]);
  end;
 sum[0]:=0;
 for i:=1 to n do
  sum[i]:=sum[i-1]+ans[i];
 {for i:=1 to len do
  writeln(z[i],' ',ans[i]);}
 for i:=1 to q do
  begin
   readln(ch,k); pp:=0;
   if k>z[len] then begin
    case ch of
    '<':writeln(sum[len]);
    '=':writeln(0);
    '>':writeln(0);
    end;
    continue;
   end;

   ll:=1; rr:=len; j:=0;
   while ll<=rr do
    begin
     mid:=(ll+rr)>>1;
     if z[mid]=k then begin
      case ch of
      '<':writeln(sum[mid-1]);
      '=':writeln(ans[mid]);
      '>':writeln(sum[len]-sum[mid]);
      end;
      j:=1; break;
     end;
     if z[mid]<k
     then ll:=mid
     else rr:=mid;
     inc(pp); if pp=20 then break;
    end;

   if j=1 then continue;

   if (z[ll]=k)or(z[rr]=k) then begin
    if z[ll]=k then mid:=ll;
    if z[rr]=k then mid:=rr;
    case ch of
    '<':writeln(sum[mid-1]);
    '=':writeln(ans[mid]);
    '>':writeln(sum[len]-sum[mid]);
    end;
    continue;
   end;

   if k<z[ll]
   then dec(ll)
   else if k>z[rr] then inc(ll);

   case ch of
   '<':writeln(sum[ll]);
   '=':writeln(0);
   '>':writeln(sum[len]-sum[ll]);
   end;
  end;
 close(input); close(output);
end.