Nhận xét: Số lần swap của thuật toán bằng với số lần swap khi ta thực hiện thuật toán sau:

for i = n - 2 to 0:
    for j = i + 1 to n - 1:
        if a[j] < a[j - 1]:
            swap(a[j], a[j - 1])

Với thuật toán trên, khi xét đến một ~a_i~ nào đó thì dãy ~a_{i+1},a_{i+2},\dots, a_{n-1}~ đã được sắp xếp. Khi đó số lần swap để ~a_i~ về đúng vị trí là: ~0~ nếu ~a_i=0~ và bằng số lượng số ~a_j=0~ với ~j=i+1\dots n-1~ nếu ~a_i=1~.

Như vậy, gọi ~cnt_i~ là số lượng ~a_j=0~ với ~j=i+1\dots n-1~ thì đáp án của bài toán sẽ là ~\sum_{i=0}^{n-2} a_i\times cnt_{i+1}~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 21; 
const int MASK = (1<<17)+5;
const int MAX = 1e6+5;
const int MOD = 998244353;
const int SQRT = 316;
const ll INF = 2e9;
const ll lon = 1e18;

int n;
int a[MAX];

ll solve() {
    ll res = 0, pos = 0;
    fo(i, 1, n) {
        if(a[i] == 1) continue;
        pos++;
        res += i-pos;
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n;
    fo(i, 1, n) cin >> a[i];
    cout << solve();
}