【题目描述】

小A打算开始炼NOI元丹（什么鬼），据说吃了可以提高NOI时的成绩。

是这么练的。元丹有三种元核，’N’,’O’,’I’。现有很多个这样原核，按顺序排成一行。炼元丹时，从左往右分别挑出’N’,’O’,’I’三个原核吞下。

现在他关心，有几种服用方式……且慢！

他觉得服用方式太少，以至于不能成仙。所以他可以通过某个途径，得到’N’,’O’,’I’的三种原核中的任意一个，至于哪一种由他决定。然后他将获得这个原核的插入到这一排原核中的任意位置（包括最前最后）。

现在你要知道，新的元核序列中能有多少种’N’,’O’,’I’的取出方式。子串的字母并不要求连续。

【输入格式】

第一行，一个整数N，表示字符串的长度。

第二行，一行字符串，里面只有只有’N’,’O’,’I’三种字母。

【输出格式】

表示出最多可以提炼出来的NOI元丹的方案种数。

【样例输入】

5

NOIOI

【样例输出】

6

【分析】

如果不能插入新的字母就太简单了，可是这题要插入新的字母。

如果要插入N，那么这个N一定插在序列最前面，这个画个图就能证明。

如果要插入I，那么这个I一定插在序列最后面，与上同理。

如果要插入O，那么设leftn[i]表示第i个字母左边N的个数，righti[i]表示第i个字母右边I的个数，枚举使leftn[x]*right[x]最大的x即可。

var  i,n,p:longint;    leftn,righti:array[0..100001]of qword;    ans,t,tt:qword;    s,s1:ansistring;function max(x,y:qword):qword;begin  if x>y then exit(x) else exit(y);end;function search(st:ansistring):qword;var  f:array[1..3]of qword;    ch:char;    i:longint;begin  fillchar(f,sizeof(f),0);  for i:=1 to n+1 do begin    ch:=st[i];    if ch='N' then f[1]:=f[1]+1;    if ch='O' then f[2]:=f[2]+f[1];    if ch='I' then f[3]:=f[3]+f[2];  end;  exit(f[3]);end;begin  ans:=0;    readln(n);  readln(s);    n:=length(s);    s1:='N'+s;    ans:=max(ans,search(s1));    s1:=s+'I';    ans:=max(ans,search(s1));    s1:=s;    leftn[0]:=0;    for i:=1 to n do begin      leftn[i]:=leftn[i-1];      if s[i]='N' then inc(leftn[i]);    end;    righti[n+1]:=0;    for i:=n downto 1 do begin      righti[i]:=righti[i+1];        if s[i]='I' then inc(righti[i]);    end;    t:=0;    for i:=1 to n do begin      tt:=leftn[i]*righti[i];        if tt>t then begin t:=tt;p:=i; end;    end;    s1:=s;    insert('O',s1,p+1);    ans:=max(ans,search(s1));    write(ans);end.