题目分析

这个问题有一个关键特性：数字只能被添加到序列的最左端或最右端。这意味着最终生成的序列实际上是由一个递减序列（从左边添加的数字）和一个递增序列（从右边添加的数字）拼接而成，且这两个序列在原输入序列中的顺序是相反的。

例如，对于输入 [2, 1, 3, 4]，一种可能的操作是：

• 将 2 放在中间
• 将 1 放在左边 -> [1, 2]
• 将 3 放在右边 -> [1, 2, 3]
• 将 4 放在右边 -> [1, 2, 3, 4]

最终序列是 [1, 2, 3, 4]，其中 [1] 是左边部分（递减序列的反向），[2, 3, 4] 是右边部分（递增序列）。

关键观察

1. 最长上升子序列（LIS）的结构：

   • 最终序列 = 左边递减序列的反向 + 右边递增序列
   • 整个序列的LIS实际上主要来自右边递增序列，因为左边递减序列本身是递减的，不会产生长的上升序列
   • 但是，左边序列的最大值如果小于右边序列的最小值，那么整个序列可能形成一个更长的上升序列

2. 重要结论：

   • 实际上，最长严格上升子序列的长度等于：不同数字的个数
   • 因为对于每个数字，我们都可以通过选择添加到左边还是右边，使得它出现在最终LIS中的合适位置

3. 方案数计算：

   • 对于每个数字，如果它既可以在左边又可以在右边，那么就有2种选择
   • 但是有些数字可能只能放在一边（比如最小值只能放在右边，最大值只能放在左边）
   • 方案数 = 所有数字的选择数的乘积

算法思路

1. 求最长上升子序列长度：

   • 统计输入序列中不同数字的个数
   • 这就是答案的长度

2. 求方案数：

   • 对序列中的每个数字，判断它能放在左边还是右边
   • 如果一个数字比它前面所有数字都大，那么它只能放在左边
   • 如果一个数字比它后面所有数字都小，那么它只能放在右边
   • 否则，它可以放在左边或右边（2种选择）
   • 方案数 = 所有数字选择数的乘积 mod 10^9+7

代码实现

MOD = 10**9 + 7

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    arr = list(map(int, data[1:1+n]))
    
    # 最长上升子序列长度 = 不同数字的个数
    lis_length = len(set(arr))
    
    # 计算每个数字能放在左边还是右边
    # 预处理前缀最小值和后缀最大值
    prefix_min = [0] * n
    suffix_max = [0] * n
    
    prefix_min[0] = arr[0]
    for i in range(1, n):
        prefix_min[i] = min(prefix_min[i-1], arr[i])
    
    suffix_max[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        suffix_max[i] = max(suffix_max[i+1], arr[i])
    
    # 计算方案数
    ways = 1
    for i in range(n):
        choices = 0
        # 如果能放在左边
        if i == 0 or arr[i] > prefix_min[i-1]:
            choices += 1
        # 如果能放在右边  
        if i == n-1 or arr[i] < suffix_max[i+1]:
            choices += 1
        
        ways = (ways * choices) % MOD
    
    print(f"{lis_length} {ways}")

if __name__ == "__main__":
    solve()

样例验证

样例1：

输入: 
2
1 1

输出:
1 4

解释：不同数字只有{1}，所以LIS长度为1。每个数字都有2种选择（左或右），所以方案数 = 2 × 2 = 4。

样例2：

输入:
4  
2 1 3 4

输出:
4 1

解释：不同数字有{1,2,3,4}，所以LIS长度为4。只有一种放置方式能得到完整的上升序列[1,2,3,4]。

复杂度分析

• 时间复杂度：O(N)，只需要三次线性扫描
• 空间复杂度：O(N)，用于存储前缀最小值和后缀最大值数组

这个解法利用了题目的特殊性质，避免了传统的O(N²)或O(NlogN)的LIS算法，实现了线性时间复杂度。