#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int n, q; int a[200010]; int d[110]; long long s[110]; int b[200010]; int t[200010]; long long merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; // int mid = (l + r) / 2; long long cnt = merge_sort(l, mid); cnt += merge_sort(mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (b[i] <= b[j]) t[k++] = b[i++]; else { t[k++] = b[j++]; cnt += mid - i + 1; } } while (i <= mid) t[k++] = b[i++]; while (j <= r) t[k++] = b[j++]; for (k = l; k <= r; k++) b[k] = t[k], t[k] = 0; return cnt; } int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } long long ans = merge_sort(1, n); for (int i = 1; i <= n; i++) d[1]++, d[a[i]]--; while (q--) { int op; cin >> op; if (op == 1) { int x; cin >> x; for (int i = 1; i <= 100; i++) s[i] = s[i - 1] + d[i]; ans += s[x]; d[1]++, d[x]--; a[++n] = x; } else { if (n == 2) { ans = 0; continue; } int x = a[n]; for (int i = 1; i <= 100; i++) s[i] = s[i - 1] + d[i]; ans -= s[x]; d[1]--, d[x]++; n--; } cout << ans << endl; } return 0; }