If the elements of \(A\) are pairwise distinct, for any \(i,j\ (1 \leq i \lt j \leq N)\), the following property holds.

• There are \(2^{j-i-1}\) (not necessarily consecutive) subsequences of \(A\), \(A'=(A'_1,A'_2,\ldots,A'_k)\), such that \(A'_1=A_i\) and \(A'_k=A_j\).

Therefore, if the elements of \(A\) are pairwise distinct, the answer is as follows.

• The sum of \(2^{j-i-1}\) over all pairs of integers \((i,j)\) such that \(1 \leq i \lt j \leq N\) and \(A_i \leq A_j\)

Since \(2^{j-i-1}=\frac{2^{j-1}}{2^i}\), we can obtain the following fact.

• For each \(j=1,2,\ldots,N\), let \(B_j=(\)the sum of \(\frac{1}{2^i}\) over all integers \(i\) such that \(1 \leq i \lt j\) and \(A_i \leq A_j)\). Then the answer is \(\sum_{j=1}^{N} B_j \times 2^{j-1}\).

Therefore, once we have found \(B_j\) for \(j=1,2,\ldots,N\), it is easy to find the answer.

Finding \(B_j\) is not so difficult; it can be found in a total of \(O(N \log N)\) time by coordinate-compressing the elements of \(A\) and scanning them in the increasing order of indices, using Binary Indexed Tree. Here, it is difficult to manage \(\frac{1}{2^i}\) with decimal numbers, so it is recommended to manage them with the inverse on \(\text{mod}\ 998244353\).

Even if the elements of \(A\) is not pairwise distinct, the answer can be found in the similar way. Therefore, the problem has been solved.

The time complexity is, depending on implementation, \(O(N \log N)\) or \(O(N \log \text{mod})\) (where the latter is one when the inverse is computed every time).

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const ll mod = 998244353;

struct binary_indexed_tree{
    int N;
    vector<ll> bit;
    binary_indexed_tree(int n):N(n){
        bit.resize(N+1,0);
    }
    ll addition(ll x, ll y){
        return (x+y)%mod;
    }
    void add(int x,ll a){
        x++;
        for(x; x<=N; x+=(x&-x)) bit[x] = addition(bit[x],a);
    }
    ll sum(int x){
        x++;
        ll ret=0;
        for(x; x>0; x-=(x&-x)) ret = addition(ret,bit[x]);
        return ret;
    }
};

ll modpow(ll x, ll y){
    ll ret = 1;
    while(0 < y){
        if(y & 1){
            ret *= x;
            ret %= mod;
        }
        x *= x;
        x %= mod;
        y >>= 1;
    }
    return ret;
}

int comp(vector<int> &A){
    std::map<int,int> mem;
    for(auto p: A) mem[p] = 0;
    int sz = 0;
    for(auto &p: mem) p.second = sz++;
    for(auto &p: A) p = mem[p];
    return sz;
}

int main(){
    const ll div = modpow(2,mod-2);
    int N; cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    int n = comp(A);
    binary_indexed_tree bit(n);
    ll ans = 0;
    for(int i=0; i<N; i++){
        ans += bit.sum(A[i])*modpow(2,i);
        ans %= mod;
        bit.add(A[i],modpow(div,i+1));
    }
    cout << ans << endl;
}