Vì mọi giá ~a_i~ là khác nhau, ta tưởng tượng mỗi giá trị ~a_i~ là một đỉnh khác nhau trên đồ thị. Ta dựng đồ thị: với với mỗi giá trị ~x~ có thể biến thành giá trị ~y~ trong ~1~ giây, ta xem y như đỉnh cha của ~x~ hay nói bằng cách khác ~a_i~ sẽ có đỉnh cha là ~a_{b_i}~ và ~1~ sẽ có đỉnh cha là ~0~. Để tìm ~b_i~ với mọi ~i~ từ một tới ~n~ ta có thể dùng Segment Tree hoặc Monotonic Queue.

Ta thấy rằng sau từng giây, với mọi ~i~ từ ~1~ tới ~n~:

1. Nếu ~a_i~ lớn hơn ~0~ thì ~a_i~ sẽ giảm.
2. Nếu ~a_i~ bằng ~0~ thì sẽ giữ nguyên bằng ~0~.

Từ đó suy ra, đồ thị này sẽ liên thông vì mọi giá trị đều có thể trở thành ~0~ bằng cách đi qua các cạnh (mọi giá trị đều giảm hoặc bằng ~0~). Mọi đỉnh đều chỉ tạo ra ~1~ cạnh nối với cha của nó trừ đỉnh ~0~ nên đồ thị sẽ có ~n~ cạnh và ~n + 1~ đỉnh. ~\rightarrow~ Đồ thị trên là cây.

Tới đây thì cách làm trở nên đơn giản. Gọi ~dp_i~ là thời gian để giá trị ~i~ có thể trở thành một giá trị bé hơn hoặc bằng ~x~, ta đi từ đỉnh gốc (đỉnh ~0~) tới các đỉnh con của nó. Xét tới đỉnh ~v~, gọi cha của ~v~ là ~u~, ta có:

1. Nếu ~v \leq x~, ~dp_v = 0~
2. Nếu ~v > x~, ~dp_v = dp_u + 1~

Để trả lời một truy vấn thì ta cần đếm số lượng ~dp_i~ nhỏ hơn hoặc bằng ~k~. Sắp xếp lại mảng ~dp~, câu trả lời cho mỗi truy vấn ~k~ là ~dp_k~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)5e5+228;
const int INF = (int)1e9;

struct BinaryIndexTree
{
    vector<int> tree;
    int n;
    BinaryIndexTree(int _n = 0, int _v = 0)
    {
        n = _n;
        tree.assign(n+7, _v);
    }
    void upd1(int x, int v)
    {
        for(int i=x; i<=n; i+=(i&-i))
        {
            tree[i] = max(tree[i], v);
        }
    }
    int calc1(int x)
    {
        int res = 0;
        for(int i=x; i>=1; i-=(i&-i))
        {
            res = max(res, tree[i]);
        }
        return res;
    }

    void upd2(int x, int v)
    {
        for(int i=x; i<=n; i+=(i&-i))
        {
            tree[i] = min(tree[i], v);
        }
    }
    int calc2(int x)
    {
        int res = n+1;
        for(int i=x; i>=1; i-=(i&-i))
        {
            res = min(res, tree[i]);
        }
        return res;
    }
}bit1, bit2;

int n, q, x;
int l[N], r[N], b[N], a[N];
int dp[N], cnt[N];

int calc(int i)
{
    if(dp[i] != -1) return dp[i];
    if(a[i] <= x) return dp[i] = 0;
    return dp[i] = 1 + calc(b[i]);
}

void solve()
{
    cin >> n >> q >> x;
    for(int i=1; i<=n; ++i) cin >> a[i], b[i] = i;

    bit1 = BinaryIndexTree(n, 0);
    for(int i=1; i<=n; ++i)
    {
        l[i] = bit1.calc1(a[i]);
        bit1.upd1(a[i], i);
    }

    bit2 = BinaryIndexTree(n, n+1);
    for(int i=n; i>=1; --i)
    {
        r[i] = bit2.calc2(a[i]);
        bit2.upd2(a[i], i);
    }

    for(int i=1; i<=n; ++i)
    {
        if(l[i] >= 1)
        {
            if(r[i] <= n)
            {
                if(i - l[i] == r[i] - i)
                {
                    if(a[l[i]] > a[r[i]]) b[i] = l[i];
                    else b[i] = r[i];
                }
                else if(i - l[i] < r[i] - i) b[i] = l[i];
                else b[i] = r[i];
            }
            else b[i] = l[i];
        }
        else if(r[i] <= n) b[i] = r[i]; 
        else b[i] = 0;
    }

    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=n; ++i) dp[i] = calc(i), cnt[dp[i]]++;
    for(int i=1; i<=n; ++i) cnt[i] += cnt[i-1];

    while(q--)
    {
        int k; cin >> k;
        cout << lower_bound(cnt, cnt+n+1, k) - cnt << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}