vector 与 multiset 相同操作时间复杂度

vector<int> A;
int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
	for (int i = 1; i <= n; ++i) {
		A.insert (lower_bound (A.begin (), A.end (), a[i]), a[i]);
		int f = 0;
		for (auto j : A) {
			if (f > j) f--;
			else if (f < j) f++;
		}
		printf ("%d\n", f);
	}
	return 0;
}

multiset<int> s;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		s.insert(a[i]);
		int ans = 0;
		for (auto j : s) {
			if (ans < j) {
				ans++;
			} else if (ans > j) {
				ans--;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}