我有一个关于时间复杂度的小问题。我搞出了一个暴力算法：

#include <bits/stdc++.h>

using namespace std;

typedef double db;

const int MAXN = 1e6 + 10;

int n, k;

db a[MAXN], sum;

bool f;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &a[i]);
    do {
        f = 0, sum = 0, k = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] > a[i - 1]) {
                if (a[i - 1] != a[k]) f = 1;
                sum /= i - k;
                for (int j = k; j < i; j++) a[j] = sum;
                sum = 0, k = i;
            }
            sum += a[i];
        }
        if (a[k] != a[n]) {
            f = 1;
            sum /= n - k + 1;
            for (int j = k; j <= n; j++) a[j] = sum;
        }
    } while (f);
    for (int i = 1; i <= n; i++) printf("%.9lf\n", a[i]);
}

该算法的本质就是将一段最长不上升子段变为他们的平均数。考虑最坏情况，将每段最长不上升子段摊平，那么每次最少将两段相同的数摊平为一段，外层循环的执行次数应该是 $O(\log n)$，内层的复杂度显然为 $O(n)$，总复杂度应该是 $O(n\log n)$。可是，在本题 $n\le10^6$ 的数据下，他成功地获得了 Time limit exceeded on test 44。求助大佬分析复杂度