#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
typedef long long ll;

struct tree {
    int l,r;
    ll sum,add;
}tr[4*N];
int a[N];

void pushup(int c) {
    tr[c].sum = tr[c<<1].sum+tr[c<<1|1].sum;
}

void pushdown(int c) {
    if (tr[c].l == tr[c].r) return;
    auto &root = tr[c], &left = tr[c<<1], &right = tr[c<<1|1];
    left.add += root.add; left.sum += (ll)(left.r-left.l+1)*(root.add);
    right.add += root.add; right.sum += (ll)(right.r-right.l+1)*(root.add);
    root.add = 0;
}

void build(int c, int l, int r) {
    if (l == r) tr[c] = {l,r,a[l],0};
    else {
        tr[c] = {l,r};
        int mid = l+r>>1;
        build(c<<1,l,mid);build(c<<1|1,mid+1,r);
        pushup(c);
    }
}

void modify(int c, int l, int r, int x) {
    if (l <= tr[c].l && tr[c].r <= r) {
        tr[c].sum += (ll)(tr[c].r - tr[c].l + 1)*x;
        tr[c].add += x;
    } else {
        pushdown(c);
        int mid = tr[c].l+tr[c].r>>1;
        if (l <= mid) modify(c<<1,l,r,x);
        if (r > mid) modify(c<<1|1,l,r,x);
        pushup(c);
    }
}


ll query(int c, int l, int r) {
    if (l <= tr[c].l && tr[c].r <= r) {
        return tr[c].sum;
    } else {
        pushdown(c);
        ll ans = 0;
        int mid = tr[c].l+tr[c].r>>1;
        if (l <= mid) ans = query(c<<1,l,r);
        if (r > mid) ans += query(c<<1|1,l,r);
        pushup(c);
        return ans;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);
    build(1,1,n);

    while (m--) {
        char op[4]; int l, r; scanf("%s%d%d",op,&l,&r);
        if (*op == 'Q') {
            printf("%lld\n",query(1,l,r));
        } else {
            int x; scanf("%d",&x);
            modify(1,l,r,x);
        }

    }

    return 0;
}

#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 2*1e5+10;

struct tree {
    int l,r;
    int v;
}tr[4*N];

void build(int cur, int l, int r)
{
    tr[cur] = {l,r};
    if (l == r) return;
    int mid = l+r>>1;
    build(cur<<1,l,mid);build(cur<<1|1,mid+1,r);
}

void pushup(int cur) {
    tr[cur].v = max(tr[cur<<1].v, tr[cur<<1|1].v);
}

int quiry(int cur, int l, int r)
{
    if (tr[cur].l >= l && tr[cur].r <= r) return tr[cur].v;
    int ans = 0;
    int mid = tr[cur].l + tr[cur].r >> 1;
    if (l <= mid) ans = quiry(cur<<1,l,r);
    if (r > mid) ans = max(ans,quiry(cur<<1|1,l,r));
    return ans;
}


void modify(int cur, int x, int v) {
    if (tr[cur].l == x && x == tr[cur].r) tr[cur].v = v;
    else {
        int mid = tr[cur].l + tr[cur].r >> 1;
        if (mid >= x) modify(cur<<1,x,v);
        else modify(cur<<1|1,x,v);
        pushup(cur);
    }
}


int main()
{
    int m,p; scanf("%d%d",&m,&p);
    build(1,1,m);
    int n = 0;
    int a = 0;

    while (m--) {
        char op[2]; int x; scanf("%s%d",op,&x);
        if (*op == 'Q') {
           a = quiry(1,n-x+1,n);
           printf("%d\n",a);
        } else {
            modify(1,++n,(x+a)%p);
        }
    }

    return 0;
}

#include <iostream>
using namespace std;
#include <cmath>
const int N = 200010;

int dp[20][N];

int main()
{
    int n; scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&dp[0][i]);

    for (int i = 1; i <= 20; ++i) {
        int t = n - (1<<i) + 1;
        if (t < 1) break;
        for (int k = 1; k <= t; ++k) {
            dp[i][k] = max(dp[i-1][k], dp[i-1][k+(1<<(i-1))]);
        }
    }

    int m; scanf("%d",&m);
    for (int i = 1; i <= m; ++i) {
        int l,r; scanf("%d%d",&l,&r);
        int j = log2(r-l+1);
        printf("%d\n", max(dp[j][l],dp[j][r-(1<<j)+1]));
    }
    return 0;
}

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;
typedef long long ll;
ll tr1[N];
ll tr2[N];
int a[N];
int n,m;

int lowbit(int x) {
    return x&-x;
}

void add(ll tr[], int x, ll c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

ll sum(ll tr[], int x) {
    ll res = 0;
    for (int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}


ll psum(int x) {
    return sum(tr1,x)*(x+1) - sum(tr2,x);
}



int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) {
        int b = a[i] - a[i-1];
        add(tr1,i,b);
        add(tr2,i,(ll)b*i);
    }

    while (m--) {
        char ch[4]; scanf("%s",ch);
        if (ch[0] == 'Q') {
            int l,r; scanf("%d%d",&l,&r);
            printf("%lld\n", psum(r)-psum(l-1));
        } else {
            int l,r,d; scanf("%d%d%d", &l,&r,&d);

            add(tr1,l,d);add(tr1,r+1,-d);

            add(tr2,l,(ll)d*l);add(tr2,r+1,(ll)-d*(r+1));
        }
    }

    return 0;
}

#include <cstdio>
#include <iostream>

using namespace std;
int n;
const int N = 100010;
int tr[N];
int a[N];
int h[N];

int lowbit(int x) {
    return x&-x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() 
{
    scanf("%d",&n);
    for (int i = 2; i <= n; ++i) scanf("%d",&h[i]);

    for (int i = 1; i <= n; ++i) tr[i] = lowbit(i);

    for (int i = n; i ; --i) {
        int k = h[i]+1;
        int l = 1, r = n;
        while (l < r) {
            int mid = l+r>>1;
            if (sum(mid) < k) l = mid+1;
            else r = mid;
        }
        a[i] = r;
        add(r,-1);
    }

    for (int i = 1; i <= n; ++i) printf("%d\n", a[i]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;

const int N = 1e5+10;
ll tr[N];
int a[N];
int n,m;

int lowbit(int x) {
    return x&-x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

ll sum(int x) {
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);


    for (int i = 1; i <= n; ++i) {
        add(i,a[i]);
        add(i+1,-a[i]);
    }

    while (m--) {
        char ch[4]; scanf("%s",ch);
        if (ch[0] == 'Q') {
            int x; scanf("%d", &x);
            printf("%lld\n",sum(x));
        } else {
            int l,r,d; scanf("%d%d%d",&l,&r,&d);
            add(l,d);
            add(r+1,-d);
        }
    }


    return 0;
}

#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;

int n;
const int N = 200010;
int g[N],l[N];
int tr[N];
int a[N];

int lowbit(int x) {
    return x&-x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);
    for (int i = 1; i <= n; ++i) {
        int y = a[i];
        g[i] = sum(n) - sum(y);
        l[i] = sum(y-1);
        add(y,1);
    }

    memset(tr,0,sizeof(tr));
    long long res1 = 0, res2 = 0;
    for (int i = n; i ; --i) {
        int y = a[i];
        res1 += g[i] * (long long)(sum(n) - sum(y));
        res2 += l[i] * (long long)(sum(y-1));
        add(y,1);
    }

    printf("%lld %lld", res1, res2);
    return 0;

}

#include <iostream>
using namespace std;
const int N = 6010;
int h[N],e[N],ne[N],cur=1;
int hi[N];
int dp[N][2];
int child[N];

void add(int a, int b)
{
    e[cur] = b; ne[cur] = h[a]; h[a] = cur++;
}

void dfs(int c)
{
    dp[c][1] = hi[c];
    for (int i = h[c]; i; i = ne[i]) {
        dfs(e[i]);
        dp[c][1] += dp[e[i]][0];
        dp[c][0] += max(dp[e[i]][0], dp[e[i]][1]);
    }
}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> hi[i];
    }
    for (int i = 1; i < n; ++i) {
        int l,k; cin >> l >> k;
        add(k,l);
        child[l] = 1;
    }

    int root = 1;
    while (child[root]) ++root;
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int dp[N];

int main()
{
    int n; cin >> n;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = (dp[j]+dp[j-i])%1000000007;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 310;
int nums[N][N], dp[N][N];
int n,m;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int f(int x, int y) 
{
    auto &v = dp[x][y];
    if (v) return v;
    v = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx <= n && ny <= m && nx > 0 && ny > 0 && nums[x][y] > nums[nx][ny])
            v = max(v,f(nx,ny)+1);
    }
    return v;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> nums[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ans = max(ans,f(i,j));
        }
    }
    cout << ans << endl;
    return 0;
}