#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 5 "library2/algorithm/run_length.hpp"
template <class T> std::vector<std::pair<T, int>> RunLength(const std::vector<T> &x) {
std::vector<std::pair<T, int>> ret;
if (x.empty()) {
return ret;
}
const int n = len(x);
for (int l = 0; l < n;) {
int r = l + 1;
while (r < n and x[l] == x[r]) {
++r;
}
ret.push_back({x[l], r - l});
l = r;
}
return ret;
}
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 2 "library2/utility/rec_lambda.hpp"
template <class F> class RecursiveLambda {
F f;
public:
explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
template <class... Args> constexpr auto operator()(Args &&...args) const {
return f(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/scan.hpp"
template <typename T = int> T scan() {
T ret;
std::cin >> ret;
return ret;
}
#line 9 "paper.cpp"
i64 solve1d(std::vector<i64> X, std::vector<i64> Y) {
const int N = len(X);
std::map<i64, std::vector<i64>> points;
for (const int i : rep(N)) {
points[X[i]].push_back(Y[i]);
}
auto parse = [](std::vector<i64> &vec) {
const int n = len(vec);
for (const int i : rep(n)) {
vec[i] -= i;
}
const auto res = RunLength(vec);
std::vector<std::pair<i64, i64>> ret;
int count = 0;
for (const auto &[value, length] : res) {
ret.push_back({value + count, value + count + length});
count += length;
}
return ret;
};
std::vector<i64> count(N);
std::vector<std::vector<int>> tree(N);
auto make_tree = [&]() {
std::vector<std::pair<i64, i64>> last;
int cum = 0;
int last_f = 0;
for (auto &[key, vec] : points) {
std::sort(vec.begin(), vec.end());
const auto res = parse(vec);
for (const auto e : res) {
const auto l = e.first, r = e.second;
count[cum] = r - l;
const int l_l = (int)(std::partition_point(last.begin(), last.end(),
[&](const std::pair<i64, i64> &v) {
return v.second <= l;
}) -
last.begin());
const int l_r = (int)(std::partition_point(last.begin(), last.end(),
[&](const std::pair<i64, i64> &v) {
return v.first < r;
}) -
last.begin());
for (const int i : rep(l_l, l_r)) {
tree[last_f + i].push_back(cum);
tree[cum].push_back(last_f + i);
}
++cum;
}
last = res;
last_f = cum - len(res);
}
count.erase(std::find_if(count.begin(), count.end(), [](const int v) { return v == 0; }),
count.end());
tree.erase(tree.begin() + len(count), tree.end());
};
make_tree();
// sum[dist(u, v) * count(u) * count(v)]
i64 ret = 0;
auto calc = rec_lambda([&](auto &&f, const int v, const int p) -> std::pair<i64, i64> {
if (v != 0 and tree[v].size() == 1) {
return {count[v], count[v]};
}
i64 dicsum = 0, udcsum = 0;
for (const int to : tree[v]) {
if (to == p) {
continue;
}
const auto res = f(to, v);
ret += res.first * udcsum + dicsum * res.second;
ret += res.first * count[v];
dicsum += res.first;
udcsum += res.second;
}
udcsum += count[v];
return {dicsum + udcsum, udcsum};
});
calc(0, N);
return ret;
}
int DistanceSum(int N, int *X, int *Y) {
std::vector<i64> x(N), y(N);
for (const int i : rep(N)) {
x[i] = X[i];
y[i] = Y[i];
}
return (int)((solve1d(x, y) + solve1d(y, x)) % 1000000000);
}
