虽然老师讲了，但我还是不会……

如何求本质不同的最长上升子序列的数量或者说本质不同如何处理?（本质不同：如 1 2 1 2中 {1, 2} 与 {1, 2} 本质相同，只算一种）

这是不考虑本质的计数代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'

typedef long long ll;
typedef double db;
const int M = 2e5 + 10;
const int mod = 1e9 + 7;

int n, len;
ll ans;
int a[M], dp[M], g[M];//g 二分中的辅助数组，表示所有长度为 i 的上升子序列中尾部元素的最小值
// dp 表示以 i 结尾的最长上升子序列长度
ll cal[M];// cal 表示以 i 结尾的最长上升子序列个数
vector<ll> his[M], sum[M];//his 更新历史, sum his 中的 cal[his[i][j]] 的前缀和数组
int getsum(int x) {
	int le = dp[x] - 1;
	int l = 0, r = his[le].size() - 1;
	if (r < 0) return 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (his[le][mid] >= a[x]) l = mid + 1;
		else r = mid;
	}
	return (sum[le].back() - (l ? sum[le][l - 1] : 0) + mod) % mod;
}

signed main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], g[i] = INF;
	for (int i = 1; i <= n; i ++) {
		int l = 1, r = len;
		while (l < r) {
			int mid = (l + r) / 2;
			if (g[mid] >= a[i]) r = mid;
			else l = mid + 1;
		}
		if (a[i] > g[len]) {
			g[++ len] = a[i];
			dp[i] = len;
			cal[i] = getsum(i) % mod;
			his[len].push_back(a[i]), sum[len].push_back(cal[i]);
		} else {
			dp[i] = l;
			cal[i] = getsum(i) % mod;
			if (a[i] < g[l]) {
				his[l].push_back(a[i]);
				ll ps = (sum[l].back() + cal[i]) % mod;
				sum[l].push_back(ps);
			}
			g[l] = min(g[l], a[i]);
		}
	}
	for (int i = 1; i <= n; i ++) if (dp[i] == len) ans = (ans + cal[i]) % mod;
	cout << len << ' ' << ans << endl;
	return 0;
}