给你一个长为n的序列a和一个常数k

有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k

如果这一次查询无解，输出"Chtholly"

输入描述:

第一行三个数n,m,k 第二行n个数表示这个序列a 之后m行，每行给出两个数l r表示一次询问

输出描述:

输出m行，每行一个整数，表示答案

示例1

输入

5 5 72 3 2 3 43 34 45 51 52 4

输出

1112

备注:

对于100%的数据，1 <= n , m <= 1000000 , 1 <= a_i , k <= 1000000000

思路分析 ： 利用ST表，ST[i][j] 表示以 i 为起点，跳跃 2^j 所到达的点 代码示例：

#define ll long longconst ll maxn = 1e6+5;const double pi = acos(-1.0);const ll inf = 0x3f3f3f3f; ll n, m, k;ll st[maxn][25];ll a[maxn];ll sum[maxn], cnt[maxn];ll l, r;ll LOG[maxn]; void init(){    for(ll i = 1; i <= 20; i++){        for(ll j = 1; j <= n; j++){            //st[i][j] = st[st[i][j-1]][j-1];            st[j][i] = st[st[j][i-1]][i-1];        }    }   } int main() {    //freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    cin >>n >> m >> k;    for(ll i = 1; i <= n; i++){        scanf("%lld", &a[i]);        sum[i] = sum[i-1] + a[i];        cnt[i] = cnt[i-1];        if (a[i] > k) cnt[i]++;           }       for(ll i = 1; i <= n; i++){        ll pos = upper_bound(sum+1, sum+1+n, sum[i-1]+k)-sum;        st[i][0] = pos;       //prllf("%d ", pos);    }    init();    //prllf("---- %d\n", st[2][0]);    for(ll i = 1; i <= m; i++){        scanf("%lld%lld", &l, &r);        if (cnt[r]-cnt[l-1] > 0) printf("Chtholly\n");        else {            ll ans = 0, p = l;            for(ll j = 20; j >= 0; j--){                if(st[p][j] && st[p][j] <= r){                    ans += 1<