Language: C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

template<typename T>
class BITree {
    public:
        BITree(int n) : m_N(n + 1) { m_Tree.assign(m_N, 0); }
        // [1, i] の合計値を返す (log m_N)
        // 閉区間であることに注意
        T Sum(int i) {
            if(i < 1 || i >= m_N) { return 0; }
            T s = 0;
            while(i > 0) { s += m_Tree[i]; i -= i & -i; }
            return s;
        }
        // [i, j] の合計値を返す (log m_N)
        // i < j
        // 閉区間であることに注意
        T Sum(int i, int j) {
            if(i > j) { return 0; }
            return Sum(j) - Sum(i-1);
        }
        // i 番目の要素(1-indexed)に x を足して更新 O(log m_N)
        void Add(int i, T x){ while(i < m_N) { m_Tree[i] += x; i += i & -i; } }
    private:
        int m_N;            // 要素数
        vector<T> m_Tree;   // BIT 本体
};

// v の各値を数値の大小関係はそのままに 1 から v.size() の範囲に圧縮する
template<typename T>
vector<T> VectorNormalization(const vector<T>& v) {
    vector<T> cp;
    vector<T> sorted;
    copy(v.begin(), v.end(), back_inserter(cp));
    copy(cp.begin(), cp.end(), back_inserter(sorted));
    sort(sorted.begin(), sorted.end());
    map<T, int> val_to_ind;
    for(int i = 0; i < sorted.size(); ++i) {
        if(val_to_ind.count(sorted[i]) == 0) { val_to_ind[sorted[i]] = i + 1; }
    }
    for(int i = 0; i < cp.size(); ++i) { cp[i] = val_to_ind[cp[i]]; }
    return std::move(cp);
}

// ある数列で x より左の x より大きい値の個数を求める
// out_v :  結果が入る vector 。 out_v[i] … i より左にある out_v[i] より大きい値の個数が入る
// p :      元の数列 (1 以上の整数)
// メモリ量 :   max(p のサイズ, p の最大値) * sizeof(T)
// 計算量 :     O(p.size() log max(p[i])) (1..N の順列なら N log N くらい)
template<typename T>
void GetLeftBiggerCnt1(vector<T>& out_v, const vector<T>& p) {
    vector<T> norm = VectorNormalization(p);
    out_v.assign(norm.size(), 0);
    T max_val = 0;
    for(auto& val : norm) { max_val = max(max_val, val); }
    BITree<T> bit(max_val);    // 以左に現れた数を BIT で管理
    for(int i = 0; i < norm.size(); ++i) {
        // ↓の +1 を抜くと自分以上のものを数えるようにできる
        out_v[i] = bit.Sum(norm[i] + 1, max_val);  // 自分より大きいものを数える
        bit.Add(norm[i], 1);   // 現れた数を更新
    }
}

// ある数列で x より左の x 以上の値の個数を求める
// out_v :  結果が入る vector 。 out_v[i] … i より左にある out_v[i] 以上の値の個数が入る
// p :      元の数列 (1 以上の整数)
// メモリ量 :   max(p のサイズ, p の最大値) * sizeof(T)
// 計算量 :     O(p.size() log max(p[i])) (1..N の順列なら N log N くらい)
template<typename T>
void GetLeftBiggerCnt2(vector<T>& out_v, const vector<T>& p) {
    vector<T> norm = VectorNormalization(p);
    out_v.assign(norm.size(), 0);
    T max_val = 0;
    for(auto& val : norm) { max_val = max(max_val, val); }
    BITree<T> bit(max_val);    // 以左に現れた数を BIT で管理
    for(int i = 0; i < norm.size(); ++i) {
        out_v[i] = bit.Sum(norm[i], max_val);  // 自分以上のものを数える
        bit.Add(norm[i], 1);   // 現れた数を更新
    }
}


// ある数列で x より左の x より小さい値の個数を求める
// out_v :  結果が入る vector 。 out_v[i] … i より左にある out_v[i] より小さい値の個数が入る
// p :      元の数列 (1 以上の整数)
// メモリ量 :   max(p のサイズ, p の最大値) * sizeof(T)
// 計算量 :     O(p.size() log max(p[i])) (1..N の順列なら N log N くらい)
template<typename T>
void GetLeftSmallerCnt1(vector<T>& out_v, const vector<T>& p) {
    GetLeftBiggerCnt2(out_v, p);
    for(int i = 0; i < out_v.size(); ++i) { out_v[i] = i - out_v[i]; }
}

// ある数列で x より左の x 以下の値の個数を求める
// out_v :  結果が入る vector 。 out_v[i] … i より左にある out_v[i] 以下の値の個数が入る
// p :      元の数列 (1 以上の整数)
// メモリ量 :   max(p のサイズ, p の最大値) * sizeof(T)
// 計算量 :     O(p.size() log max(p[i])) (1..N の順列なら N log N くらい)
template<typename T>
void GetLeftSmallerCnt2(vector<T>& out_v, const vector<T>& p) {
    GetLeftBiggerCnt1(out_v, p);
    for(int i = 0; i < out_v.size(); ++i) { out_v[i] = i - out_v[i]; }
}

ll N;
vector<ll> A;

int cnt[MAX_N] = {};     // i が出てくる数

// 位置 i より前に出てくる数 j の数
int cnt2[MAX_N][100];

// 自分より前(左) にある自分より小さい数のうち、一番右にあるものの位置
int pos[MAX_N];

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.resize(N);
    REP(i, N) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    // 0 チェック
    REP(i, N) {
        if(cnt[i] > 3) {
            return 0;
        }
        if(i > 0 && cnt[i - 1] == 0 && cnt[i] > 0) {
            return 0;
        }
    }

    REP(j, 100) {
        int tmp = 0;
        REP(i, N) {
            cnt2[i][j] = tmp;
            if(A[i] == j) {
                tmp++;
            }
        }
    }

    // pos の作成
    REP(i, N) {
        int val = A[i];
        if(val == 0) { continue; }
        for(int j = i - 1; j >= 0; --j) {
            if(A[j] == A[i] - 1) {
                pos[i] = j;
                break;
            }
        }
    }

    vector<ll> A2;
    REP(i, N) {
        A2.push_back(A[i] + 1);
    }
    vector<ll> small_v, small_eq_v;
    GetLeftSmallerCnt1(small_v, A2);
    GetLeftSmallerCnt2(small_eq_v, A2);

    ll ans = 1;
    REP(i, N) {
        int num = A[i];
        if(num == 0) { continue; }

        // 自分より前にいる、自分より少ない数
        ll all_small = small_v[i];

        // 自分より前にいる、自分 -1 より少ない数
        ll all_small2 = small_v_eq[pos[i]] - small_v[pos[i]];

        // 自分より前にいる、自分より 1 少ないものの数
        ll val1 = all_small - all_small2;

        // 自分より前にいる、自分と同じものの数
        ll val2 = small_eq_v[i] - small_v[i];

        DBG("i: %lld\n", i);
        DBG("  all_small: %lld\n", all_small);
        DBG("  pos[i]: %lld\n", pos[i]);
        DBG("  all_small2: %lld\n", all_small2);
        DBG("  val1: %lld\n", val1);
        DBG("  val2: %lld\n", val2);
        DBG("  cnt2[i][num - 1]: %lld\n", cnt2[i][num - 1]);
        DBG("  cnt2[i][num]: %lld\n", cnt2[i][num]);

        ans *= (val1 - val2);
        //ans *= cnt2[i][num - 1] - cnt2[i][num];
        ans %= MOD;
    }

    if(cnt[0] == 1) {
        ans *= 3;
        ans %= MOD;
    }
    else {
        ans *= 6;
        ans %= MOD;
    }
    printf("%lld\n", ans);

    return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:197:25: error: 'small_v_eq' was not declared in this scope; did you mean 'small_v'?
  197 |         ll all_small2 = small_v_eq[pos[i]] - small_v[pos[i]];
      |                         ^~~~~~~~~~
      |                         small_v