题解 | #有效序列的数量#

using namespace std;
int main() {
    int n ; long long sum = 0;
    scanf("%d", &n);
    int x;
    int ss[100004];  //排序
    int cc[100004];  //计数
    int m = 0;
    for(int i = 0 ; i < n ; ++i) {
        scanf("%d", &x);
        while(m > 0) {
            if(x == ss[m - 1]) {
                sum += cc[m - 1];
                ++cc[m - 1];
                if(m != 1) sum++;
                break;
            }else if(x < ss[m - 1]) {
                sum += cc[m - 1];
                m--;
            } else {
                sum++;
                ss[m] = x;
                cc[m] = 1;
                m++; break;
            }
        }
        if(m == 0) {
            ss[0] = x;
            cc[0] = 1;
            m = 1;
        }
    }
    printf("%lld", sum);
}