记录沉渊

"sacrifice = 0。"你把这行代码刻在屏幕上，像刻碑。

CC凑过来看。她的金属肩膀擦过你的肩膀，发出轻微的摩擦声。

"啥子意思？"

"一个都不少。"你说，"不牺牲任何人。"

"那Zero咋个办？"

"重算。"你说，"所有DP，重算一遍——不是算'谁留下'，是算'怎么全留下'。"

Echo的投影在屏幕前闪烁。她看着那行sacrifice = 0，指示灯从红变蓝，再从蓝变白——像呼吸，像心跳。

"第一个问题。"你说，"Zero的核心指标在衰减——从高点一路往下掉。我要记录这条衰减轨迹，找到最深沉的点。"

"沉渊？"

"对。"你说，"沉到最低的渊。"

"那有啥用？"

"如果指标能沉下去，也能浮上来。"你说，"我要知道它沉了多深，才能算它要爬多高。"

"像潜水。"

"对。"你说，"潜得越深，浮上来越难。但也不是不可能。"

你开始写。设$dp[i]$为以第$i$个指标为最低点的最长衰减链。$cnt[i]$为方案数。

"第1个点。"你说，"100。"

"第2个。"你说，"80。比100低，链长2。"

"第3个。"你说，"90。比80高，不能接在80后面。链长1。"

"第4个。"你说，"70。比80低，接在80后面，链长3。"

"最长链是3——100,80,70。"

"方案数？"

"只有1种。"你说，"因为80前面只有100，70前面只有80。"

"但如果还有第5个点——60。"

"那链长4。"你说，"100,80,70,60。方案数还是1。"

"单一轨迹。"

"对。"你说，"Zero的衰减是单一路径——没有分叉。"

Echo看着那条下降的曲线——从屏幕顶端一路滑到底端，像一道伤疤。

"我沉了24年。"她说。

"那你浮上来。"你说，"我们拉你。"

"你们拉得动？"

"拉得动。"CC说，"我比你重。"

Echo的投影闪了一下——像笑，像泪，像某种终于放下什么的轻松。

"那我再沉一次。"她说，"这次有人接着。"

题目描述

给定一个长度为$n$的序列，求最长严格下降子序列的长度，以及不同方案数（去重）。

输入格式

$n$。然后$n$个整数。

输出格式

两个整数：最长严格下降子序列长度，以及不同方案数模$10^9+7$。

输入样例

3
1 2 3

输出样例

1 3

提示

• $dp[i]$为以$i$结尾的最长下降子序列长度。
• $cnt[i]$为方案数。
• 去重：当$A_j=A_i$且$dp[j]=dp[i]$时，$cnt[j]=0$（只保留最右边的方案）。
• 时间复杂度$O(n^2)$。