#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, tree[N], a[N];

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

void update(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];
		update(i, a[i]);
	}
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			update(x, y);
		} else {
			cout << query(y) - query(x - 1) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
#define int long long
int n, a[N], b[N], id[N];
int tree[N];

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

void update(int x) {
	for (int i = x; i <= n; i+=lobit(i)) {
		tree[i]++;
	}
}

int query(int x) {
	int sum = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		sum += tree[i];
	}
	return sum;
}

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++) {
		id[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
	}
	int res = 0;
	for (int i = n; i >= 1; i--) {
	//	cout << id[i] << " ";
		//1~id[i]-1出现的次数
		if (id[i] != 1)
		res += query(id[i] - 1);
		update(id[i]);
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, ans[N], lst[N], b[N], id[N];
int a[N];
int tree[N];

struct node {
	int l, r, id;
} p[N];

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

void update(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;
}

bool cmp(node a, node b) {
	if (a.r == b.r)
		return a.l < b.l;
	else
		return a.r < b.r;
}

int main() {
	cin >> n ;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		id[i] = a[i];
	//	b[i] = a[i];
	}
//	sort(b + 1, b + n + 1);
//	for (int i = 1; i <= n; i++) {
//		id[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
//	}
	cin>>m;
	for (int i = 1; i <= m; i++) {
		int l, r;
		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[id[r]] == 0) {
				lst[id[r]] = r;
				update(r, 1);
			} else {
				update(lst[id[r]], -1);
				lst[id[r]] = r;
				update(r, 1);
			}
		}
		if (p[i].l == 1)
			ans[p[i].id] = query(p[i].r);
		else
			ans[p[i].id] = query(p[i].r) - query(p[i].l - 1);
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a[100005], tree[2][100005], q;

void add(int x, int y) {
	for (int i = x; i <= n; i += (i & (-i))) {
		tree[0][i] += y;
		tree[1][i] += (x - 1) * y;
	}
	return;
}

int qu(int x, int id) {
	int res = 0;
	for (int i = x; i >= 1; i -= (i & (-i))) {
		res += tree[id][i];
	}
	return res;
}

signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		add(i, a[i] - a[i - 1]);
	}
	while (q--) {
		int opt, x, y, z;
		cin >> opt >> x >> y;
		if (opt == 1) {
			cin >> z;
			add(x, z);
			add(y + 1, -z);
		} else {
			cout << y *qu(y, 0) - qu(y, 1) - (x - 1)*qu(x - 1, 0) + qu(x - 1, 1) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N];
int lst[N], lst2[N];
int tree[N], ans[N];
vector<int>b[N];

struct node {
	int l, r, id;
} p[N];

bool cmp(node a, node b) {
	if (a.r == b.r)
		return a.l < b.l;
	return a.r < b.r;
}

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

void update(int x, int c) {
	for (int i = x; i >= 1; i -= lobit(i)) {
		tree[i] = max(tree[i], c);
	}
}

int query(int x) {
	int res = 0;
	for (int i = x; i <= n; i += lobit(i)) {
		res = max(res, tree[i]);
	}
	return res;
}

int main() {
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	cin >> n;
	for (int i = 1; i <= 100000; i++) {
		for (int j = i; j <= 100000; j += i) {
			b[j].push_back(i);
		}
	}
	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++;
			for (auto j : b[a[r]]) {
				if (lst[j] == 0)
					lst[j] = r;
				else if (lst2[j] == 0) {
					lst2[j] = lst[j];
					lst[j] = r;
					update(lst2[j], j);
				} else {
					lst2[j] = lst[j];
					lst[j] = r;
					update(lst2[j], j);
				}
			}
		}
		ans[p[i].id] = query(p[i].l);
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, m, a[N];
int tree[N], ans[N];

struct node {
	int x, val, flag, id;
	//x坐标，val小于等于的数，flag正负，id问题编号
} line[N*2];

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

void update(int x, int c) {
	for (int i = x; i <= 2000000; 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;
}

bool cmp(node a, node b) {
	return a.x < b.x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		line[++cnt] = {l - 1, x, -1, i};
		line[++cnt] = {r, x, 1, i};
	}
	sort(line + 1, line + cnt + 1, cmp);
	int l = 0;
	for (int i = 1; i <= cnt; i++) {
		while (l < line[i].x) {
			l++;
			update(a[l], 1);
		}
		ans[line[i].id] += line[i].flag * query(line[i].val);
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, x;
int a[N], limit[N], cnt;
map<int, int>book;
int sum[N], b[N], id[N];
int tree[N];

struct node {
	int id, val;
} p[N];

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

void update(int x, int c) {
	for (int i = x; i <= n+1; 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;
}

bool cmp(node a, node b) {
	if (a.val == b.val)
		return a.id < b.id;
	return a.val < b.val;
}

int main() {
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = n + 1, r = n;
	while (r >= 1) {
		while (cnt <= m && l >= 1) {
			l--;
			book[a[l]]++;
			if (book[a[l]] == 1)
				cnt++;
		}
		limit[r] = l + 1;
		book[a[r]]--;
		if (book[a[r]] == 0)
			cnt--;
		r--;
	}
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i];
		p[i] = {i + 1, sum[i]};
	}
	p[0] = {1, 0};
	sort(p, p + n + 1, cmp);
	int res = 0;
	r = 0;
	for (int i = 0; i <= n; i++) {
		//sum[i]-sum[j]>=x
		//sum[j]<=sum[i]-x
		while (r <= n && p[r].val + x <= p[i].val)
			update(p[r].id, 1), r++;
		//从limit[i]~i中符合要求的下标
		if(p[i].id)res += (query(p[i].id) - query(limit[p[i].id] - 1)) * 2;
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] >= x)
			res--;
	}
	cout << res << endl;
	return 0;
}