struct PalindromicTree
{
    static const int __=1e5+5;
    static const int alp=26;

    static int to_idx(char ch)
    {
        return ch-'a'+1;
    }

#define fail(x) t[x].nex[0]

    struct node
    {
        int len,times,dep,nex[alp+1];
        void set(int l,int fa,int d)
        {
            len=l,nex[0]=fa,dep=d;
        }
        void clear()
        {
            len=times=0;
            mem(nex,0);
        }
    }t[__];

    char s[__<<1];

    int idx,pre,saf,l,r;

    PalindromicTree() {clear();}

    void push_back(char c)
    {
        s[++r]=c;
        for(int x;x=r-t[saf].len-1;saf=fail(saf))
            if(x>=l && s[x]==s[r])break;
        int k=to_idx(s[r]);
        if(t[saf].nex[k])saf=t[saf].nex[k];
        else
        {
            int y=fail(saf);
            for(int x;x=r-t[y].len-1;y=fail(y))
                if(x>=l && s[x]==s[r])break;
            y=t[y].nex[k];
            t[++idx].clear();
            t[idx].set(t[saf].len+2,y,t[y].dep+1);
            t[saf].nex[k]=idx,saf=idx;
        }
        if(t[saf].len==r-l+1)pre=saf;
        ++t[saf].times;
        ans+=t[saf].dep;
    }

    void push_front(char c)
    {
        s[--l]=c;
        for(int x;x=l+t[pre].len+1;pre=fail(pre))
            if(x<=r && s[x]==s[l])break;
        int k=to_idx(s[l]);
        if(t[pre].nex[k])pre=t[pre].nex[k];
        else
        {
            int y=fail(pre);
            for(int x;x=l+t[y].len+1;y=fail(y))
                if(x<=r && s[x]==s[l])break;
            y=t[y].nex[k];
            t[++idx].clear();
            t[idx].set(t[pre].len+2,y,t[y].dep+1);
            t[pre].nex[k]=idx,pre=idx;
        }
        if(t[pre].len==r-l+1)saf=pre;
        ++t[pre].times;
        ans+=t[pre].dep;
    }

    ll solve()
    {
        ll ans=0;
        for(int i=idx;i>=2;--i)
        {
            t[fail(i)].times+=t[i].times;
            ans=max(ans,1ll*t[i].times*t[i].len);
        }
        return ans;
    }

    void clear()
    {
        idx=1,pre=saf=0,l=__,r=l-1;
        t[0].clear(),t[1].clear();
        t[0].set(0,1,0),t[1].set(-1,1,0);
    }
}PT;