我居然场切了这题？？

首先离散化，记离散化后数组最大值为 $len$。

考虑数列形成的 LIS 中下标最小的数 $a_i$，多打点表就可以发现这个 LIS 其实就是由 $a_i$ 开头的 LIS 和以 $a_i$ 开头的 LDS 组成。

那我们就令 $f[i]$ 为 $a_i \sim a_n$ 经过题目中的处理后，能形成的包含 $a_i$ 的 LIS 的长度，$g[i]$ 为对应的方案数。

由上文我们可以开两个线段树维护以 $x$ 开头的 LIS 和 LDS 的长度，顺带维护方案数。这里记 $Il[x]$ 与 $Dl[x]$ 为 LIS 和 LDS 的长度，$Ic[x]$ 和 $Dc[x]$ 为 LIS 和 LDS 的方案数。（代码里由于是线段树维护直接查询了）

那么 $f[i]=max(Il[x+1] \sim Il[len])+max(Dl[1] \sim Dl[x-1])+1$，$g[i]$ 则是你选择的 $Il$ 与 $Dl$ 对应的方案数乘积再乘上 $2^{n-f[i]}$（毕竟剩余的不与 LIS 产生关系的就可以随便操作了嘛）。

那有人就要问了：剩下的 $a_1 \sim a_{i-1}$ 随便排列万一使 LIS 变长了咋办？

那不是 $f[1]\sim f[i-1]$ 才要管的事情吗？到时候自然会有更长的 LIS 替换掉这个结果。

所以话说这题的代码和 DP 有啥关系？

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define PII pair<int,int>
#define fi first
#define se second
const int N=2e5+10,P=1e9+7;
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
struct SMTree
{
	struct node{int l,r,mx,s;}tr[N<<2];
	void pushup(int p)
	{
		tr[p].mx=tr[lc(p)].mx,tr[p].s=tr[lc(p)].s;
		if(tr[rc(p)].mx>tr[p].mx)tr[p].mx=tr[rc(p)].mx,tr[p].s=tr[rc(p)].s;
		else if(tr[rc(p)].mx==tr[p].mx)tr[p].s=(tr[p].s+tr[rc(p)].s)%P;
	}
	void bt(int p,int l,int r)
	{
		tr[p]={l,r,0,0};
		if(l==r)return;
		int mid=(l+r)>>1;
		bt(lc(p),l,mid);bt(rc(p),mid+1,r);
		pushup(p);
	}
	void change(int p,int x,int k1,int k2)
	{
		if(tr[p].l>x||tr[p].r<x)return;
		if(tr[p].l==tr[p].r)
		{
			tr[p].mx=k1;tr[p].s=k2;
			return;
		}
		change(lc(p),x,k1,k2);change(rc(p),x,k1,k2);
		pushup(p);
	}
	PII query(int p,int l,int r)
	{
		if(tr[p].l>r||tr[p].r<l)return {0,0};
		if(l<=tr[p].l&&tr[p].r<=r)return {tr[p].mx,tr[p].s};
		PII ans=query(lc(p),l,r),ans1=query(rc(p),l,r);
		if(ans.fi<ans1.fi)ans=ans1;
		else if(ans.fi==ans1.fi)ans.se=(ans.se+ans1.se)%P;
		return ans;
	}
}tr[2];
int a[N],b[N];
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1;
	tr[0].bt(1,1,len);tr[1].bt(1,1,len);
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	int mx=0,ans=0;
	for(int i=n;i>=1;i--)
	{
		PII l1=tr[0].query(1,1,a[i]-1),r1=tr[1].query(1,a[i]+1,len);
		if(l1==PII{0,0})l1={0,1};if(r1==PII{0,0})r1={0,1};
		if(mx<l1.fi+r1.fi+1)mx=l1.fi+r1.fi+1,ans=l1.se*r1.se%P*qpow(2,n-l1.fi-r1.fi-1)%P;
		else if(mx==l1.fi+r1.fi+1)ans=(ans+l1.se*r1.se%P*qpow(2,n-l1.fi-r1.fi-1)%P)%P;
		PII l2=tr[0].query(1,a[i],a[i]),r2=tr[1].query(1,a[i],a[i]);
		if(l2.fi<l1.fi+1)tr[0].change(1,a[i],l1.fi+1,l1.se);
		else if(l2.fi==l1.fi+1)tr[0].change(1,a[i],l2.fi,l1.se+l2.se);
		if(r2.fi<r1.fi+1)tr[1].change(1,a[i],r1.fi+1,r1.se);
		else if(r2.fi==r1.fi+1)tr[1].change(1,a[i],r2.fi,r1.se+r2.se);
	}
	cout<<mx<<' '<<ans<<'\n';
	return 0;
}