#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int a[N],tree[N],n,m;
int lobit(int x) {
    //返回x中二进制最后一个1的位置
    return x&-x;
}
void add(int x,int c) {
    for (int i=x;i<=n;i+=lobit(i)) {
        tree[i]+=c;
    }
}
int query(int x) {
    //返回1～x的和
    int sum = 0;
    for (int i=x;i>=1;i-=lobit(i)) {
        sum+=tree[i];
    }
    return sum;
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        add(i,a[i]);
    }
    while (m--) {
        int op,x,y,z;
        cin>>op>>x;
        if (op==1) {
            cin>>y;
            add(x,y);
        }
        else {
            cin>>y;
            cout<<query(y)-query(x-1)<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m,a[N],b[N],tree[N];
int lobit(int x) {
    return x&-x;
}
void add(int x,int c) {
    for (int i=x;i<=n;i+=lobit(i))tree[i]+=c;
}
int query(int x) {
    int sum = 0;
    for (int i=x;i>=1;i-=lobit(i)) {
        sum+=tree[i];
    }
    return sum;
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        b[i] = a[i]-a[i-1];
    }
    for (int i=1;i<=n;i++) {
        add(i,b[i]);
    }
    while (m--) {
        int op,x,y,z;
        cin>>op;
        if (op==1) {
            cin>>x>>y>>z;
            add(x,z);
            add(y+1,-z);
        }
        else {
            cin>>x;
            cout<<query(x)<<endl;
        }
    }
    return 0;
}

/*
 * 离散化
 * 1 5 1000 100 3 60
 * 1 3 5 60 100 1000
 * 1 3 6 5 2 4
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,a[N],b[N],id[N],tree[N];
int lobit(int x) {
    return x&-x;
}
void add(int x,int c) {
    for (int i=x;i<=n;i+=lobit(i)) {
        tree[i]+=c;
    }
}
int query(int x) {
    int res = 0;
    for (int i=x;i>=1;i-=lobit(i)) {
        res+=tree[i];
    }
    return res;
}
signed main() {
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b+1,b+n+1);
    for (int i=1;i<=n;i++) {
        //lower_bound 找第一个大于等于x的位置
        //upper_bound 找第一个大于x的位置
        id[i] = lower_bound(b+1,b+n+1,a[i])-b;
    }
    int res = 0;
    for (int i=n;i>=1;i--) {
        if (id[i]!=1)res+=query(id[i]-1);
        add(id[i],1);
    }
    cout<<res<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5,Mod=92084931;
int n,m,a[N],sum[N],tree[N];
struct node {
    int val,id;
}p[N];
bool cmp(node a,node b) {
    if (a.val==b.val)return a.id>b.id;
    return a.val<b.val;
}
int lobit(int x) {
    return x&-x;
}
void add(int x,int c) {
    for (int i=x;i<=n+1;i+=lobit(i)) {
        tree[i]+=c;
    }
}
int query(int x) {
    int res = 0;
    for (int i=x;i>=1;i-=lobit(i)) {
        res+=tree[i];res%=Mod;
    }
    return res%Mod;
}
signed main() {
    cin>>n>>m;
    p[0].id = 1;
    p[0].val = 0;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        p[i].val = p[i-1].val+a[i]-m;
        p[i].id = i+1;
    }
    sort(p,p+n+1,cmp);
    int res = 0;
    for (int i=0;i<=n;i++) {
        res+=query(p[i].id);res%=Mod;
        add(p[i].id,1);
    }
    cout<<res<<endl;
    return 0;
}

/*
 * 区间l～r数字的种类
 * query(r)前r个数字有多少种
 * 1～l-1  0
 * l~r    x
 * 维护x颜色最后一次出现的位置
 * l~r
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
struct node {
    int l,r,id;
}p[N];
int n,m,a[N],lst[N],ans[N];
int tree[N];
int lobit(int x) {
    return x&-x;
}
void add(int x,int c) {
    for (int i=x;i<=1000000;i+=lobit(i)) {
        tree[i]+=c;
    }
}
int query(int x) {
    int res = 0;
    for (int i=x;i>=1;i-=lobit(i)) {
        res+=tree[i];
    }
    return res;
}
bool cmp(node a,node b) {
    if (a.r==b.r)return a.l<b.l;
    return a.r<b.r;
}
int main() {
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    cin>>m;
    for (int i=1;i<=m;i++) {
        cin>>p[i].l>>p[i].r;
        p[i].id = i;
    }
    sort(p+1,p+m+1,cmp);
    int r=0;
    for (int i=1;i<=m;i++) {
        while (r<p[i].r) {
            r++;
            if (!lst[a[r]]) {
                lst[a[r]] = r;
                add(r,1);
            }
            else {
                add(lst[a[r]],-1);
                lst[a[r]] = r;
                add(r,1);
            }
        }
        ans[p[i].id] = query(r)-query(p[i].l-1);
    }
    for (int i=1;i<=m;i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}