#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
const int N = 2e5 + 5;
int n, f[N];
struct Node {
int a0, a1, a2, a01, a12, a10, a21, a012, a210;
} dummy;
Node merge(Node lhs, Node rhs) {
Node res;
res.a0 = lhs.a0 + rhs.a0;
res.a1 = lhs.a1 + rhs.a1;
res.a2 = lhs.a2 + rhs.a2;
res.a01 = lhs.a0 * rhs.a1 + lhs.a01 + rhs.a01;
res.a12 = lhs.a1 * rhs.a2 + lhs.a12 + rhs.a12;
res.a10 = lhs.a1 * rhs.a0 + lhs.a10 + rhs.a10;
res.a21 = lhs.a2 * rhs.a1 + lhs.a21 + rhs.a21;
res.a012 = lhs.a0 * rhs.a12 + lhs.a01 * rhs.a2 + lhs.a012 + rhs.a012;
res.a210 = lhs.a2 * rhs.a10 + lhs.a21 * rhs.a0 + lhs.a210 + rhs.a210;
return res;
}
struct SegTree {
int size = 1;
vector<Node> seg;
void init(int sz) {
while (size < sz) size *= 2;
seg.assign(2 * size + 10, dummy);
}
void update(int pos, int v, int l, int r, int id) {
if (l == r) {
seg[id] = dummy;
if (v == 0) seg[id].a0++;
else if (v == 1) seg[id].a1++;
else seg[id].a2++;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(pos, v, l, mid, id * 2);
else update(pos, v, mid + 1, r, id * 2 + 1);
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
}
Node query(int ql, int qr, int l, int r, int id) {
if (ql <= l && r <= qr) return seg[id];
if (qr < l || r < ql) return dummy;
int mid = (l + r) / 2;
return merge(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
}
} ST;
void init(i32 _N, std::vector<i32> F, std::vector<i32> U, std::vector<i32> V,
i32 Q) {
n = _N;
ST.init(n+1);
for (int i = 0; i < n; i++) {
f[i] = F[i];
ST.update(i+1, f[i], 1, n, 1);
}
}
void change(i32 X, i32 Y) {
X++;
ST.update(X, Y, 1, n, 1);
}
int num_tours() {
Node res = ST.query(1, n, 1, n, 1);
return res.a012 + res.a210;
}
