\(l < r\) とする． \(a_{l} \leq a_{r}\) を満たしていれば，その間の項は自由に選べるので， 答えは \begin{align} \displaystyle \sum_{ l, r \in N \times N \\ l < r \\ a_{l} \leq a_{r} } 2^{r-1-l}. \end{align} これを \(r,l\) の項に分解すれば， 各 \(r\) に対して $$ \displaystyle \sum_{l < r \\ a_{l} \leq a_{r}} 2^{-l} \ \ \cdots (*) $$ が求まれば十分．
実装
\(a\) の値に対する segtree を使えば， \(O(log N)\) で \(\,(*)\) の和が求まる． \(a\) が大きいので座標圧縮する． また，for \(r \in N\) で考えれば， \(r\) の計算をしてる時点で既に \(l\) のループは終わっているので， 計算をついでに済ませることができる． つまり， \(l\) をループさせる場合よりも，ループの個数を減らせる．
注意
\(r = 0\) のときは， \(ans\) の更新はされないが，segment tree は更新される． よって，コードでは \(rep(r,n)\) で書いている．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// 座標圧縮
template<typename P>
struct Points {
Points() {}
void add(P x) {
ps.emplace_back(x);
}
void init() {
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
}
P operator[](int i) const { return ps[i];}
int operator()(const P& x) const {
return lower_bound(ps.begin(),ps.end(), x)-ps.begin();
}
int size() const { return ps.size();}
};
mint op(mint a, mint b){
return a+b;
}
mint e(){return mint(0);}
int main() {
ll n ; cin >> n;
vll a(n); cinv(a);
Points<ll> po;
rep(i,n){
po.add(a[i]);
}
po.init();
mint ans;
segtree<mint, op, e> st(po.size());
mint pow_inv = 1, pow = 1;
rep(r,n){
ll i = po(a[r]);
ans += st.prod(0, i+1) * pow / mint(2);
st.set(i, st.get(i) + pow_inv);
pow_inv /= mint(2);
pow *= mint(2);
}
cout << ans.val() << endl;
return 0;
}
