The number of possible sets of stars, of which the darkest star is the \(i\)-th star, equals \(\bigl((\)the number of indices \(j\) such that \(j\lt i\) and \(B _ j\lt B _ i)+1\bigr)\times\bigl((\) the number of indices \(j\) such that \(j\gt i\) and \(B _ j\lt B _ i)+1\bigr)\).

One can find for all \(i\) the number of indices \(j\) such that \(j\lt i\) and \(B _ j\lt B _ i\), and the number of indices \(j\) such that \(j\lt i\) and \(B _ j\lt B _ i\), in a total of \(O(N\log N)\) time, in the same manner as the algorithm to find the inversion number in \(O(N\log N)\) time. For example, we can perform an iteration in ascending order of \(i\); using a segment tree or a Fenwick tree, we can find how many \(i\) seen so far is greater or less than the current \(i\).

Based on the information obtained, the answer can be found in a total of \(O(N)\) time, so the overall time complexity is \(O(N\log N)\) time, which is fast enough.

Since \((B _ i)\) is a permutation of \((1,2,\ldots,N)\), the implementation can be simplified.

The following is sample code.

#include <iostream>
#include <ranges>
#include <atcoder/fenwicktree>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    atcoder::fenwick_tree<unsigned> bit(N);
    unsigned long ans{};
    for (const auto B : views::istream<unsigned>(cin)) {
        const unsigned long left{bit.sum(0, B)}, right{B - 1 - left};
        ans += (left + 1) * (right + 1); // (# bright stars to the left + 1) × (# bright stars to the right + 1)
        bit.add(B - 1, 1); // Update the Fenwick tree
    }
    cout << ans << endl;
    return 0;
}