🐰😺🔢 兔猫信奥学院的递增序列计数探秘 🔢😺🐰

在兔猫信奥学院的数据之厅，小兔和小猫发现了一排珍贵的能量晶柱，每根晶柱上都刻着一个整数。它们想要沿着晶柱从左到右选出一条严格递增的路径，使得路径既足够“长”又能统计出共有多少种这样的最优路线。请帮助它们计算：给定这组晶柱值 nums，最长严格递增子序列（LIS）的长度是多少，以及一共有多少条最优子序列？

输入格式

第一行：整数 n，表示晶柱数量（数组长度）。
第二行：n 个整数 nums[i]，用空格分隔。

• $1 \le n \le 10000$
• $-10^6 \le nums[i] \le 10^6$

输出格式

输出一个整数，表示最长严格递增子序列的个数。

样例 1

5
1 3 5 4 7

2

• 解释：
  最长递增子序列长度为 4，对应的路径有
  $[1,3,5,7]$ 和 $[1,3,4,7]$，共 2 条。

样例 2

5
2 2 2 2 2

5

• 解释：
  所有元素相同，最长递增子序列长度为 1，每个元素自身都是一个序列，共 5 条。

🎓 探秘提示：
本题常用 $O(n^2)$ 动态规划即可通过，但当 $n$ 较大时可能超时，可考虑高级方法如基于「耐心排序」和「树状数组」的 $O(n\log n)$ 计数方案。祝你在算法探秘中不断精进！