#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; //* ATCODER #include using namespace atcoder; typedef modint998244353 mint; //*/ /* BOOST MULTIPRECISION #include using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) template bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template T max(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template T min(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template T sum(vector &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } //https://hitonanode.github.io/cplib-cpp/segmenttree/rangetree.hpp.html // CUT begin // 逆元を要求しない領域木 template class rangetree { int n; using Pt = std::pair; std::vector _pts; std::vector> _range2yxs; std::vector> segtrees; void _set(int v, Pt p, S val) { auto i = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first})); segtrees[v].set(i, val); } void _add(int v, Pt p, S val) { auto i = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first})); segtrees[v].set(i, op(segtrees[v].get(i), val)); } S _prod(int v, Coordinate yl, Coordinate yr) const { auto comp = [&](const Pt &l, const Pt &r) { return l.first < r.first; }; auto il = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yl, yl}, comp)); auto ir = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yr, yr}, comp)); return segtrees[v].prod(il, ir); } public: rangetree() = default; void add_point(Coordinate x, Coordinate y) noexcept { _pts.emplace_back(x, y); } void build() { std::sort(_pts.begin(), _pts.end()); _pts.erase(std::unique(_pts.begin(), _pts.end()), _pts.end()); n = _pts.size(); _range2yxs.resize(n * 2); for (int i = 0; i < n; i++) _range2yxs[n + i] = {{_pts[i].second, _pts[i].first}}; for (int i = n - 1; i > 0; i--) { auto &lch = _range2yxs[i * 2]; auto &rch = _range2yxs[i * 2 + 1]; std::merge( lch.begin(), lch.end(), rch.begin(), rch.end(), std::back_inserter(_range2yxs[i])); _range2yxs[i].erase( std::unique(_range2yxs[i].begin(), _range2yxs[i].end()), _range2yxs[i].end()); } for (const auto &v : _range2yxs) segtrees.emplace_back(v.size()); } void set(Coordinate x, Coordinate y, S val) { int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y})); assert(i < n and _pts[i] == std::make_pair(x, y)); for (i += n; i; i >>= 1) _set(i, {x, y}, val); } void add(Coordinate x, Coordinate y, S val) { int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y})); assert(i < n and _pts[i] == std::make_pair(x, y)); for (i += n; i; i >>= 1) _add(i, {x, y}, val); } S prod(Coordinate xl, Coordinate xr, Coordinate yl, Coordinate yr) const { auto comp = [](const Pt &l, const Pt &r) { return l.first < r.first; }; int l = n + std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{xl, yr}, comp)); int r = n + std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{xr, yr}, comp)); S ret = e(); while (l < r) { if (l & 1) ret = op(ret, _prod(l++, yl, yr)); if (r & 1) ret = op(ret, _prod(--r, yl, yr)); l >>= 1, r >>= 1; } return ret; } S get(Coordinate x, Coordinate y) const { return prod(x, x + 1, y, y + 1); } }; int op(int a, int b){return a + b;} int e(){return 0;} // defcomp template vector compress(vector &X) { vector vals = X; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); return vals; } // ----- // importbisect template int bisect_left(vector &X, T v){ return lower_bound(X.begin(), X.end(), v) - X.begin(); } template int bisect_right(vector &X, T v){ return upper_bound(X.begin(), X.end(), v) - X.begin(); } // ----- int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector x(n), y(n); map cntx; map cnty; rangetree rt; rep(i,0,n){ cin >> x[i] >> y[i]; cntx[x[i]]++; cnty[y[i]]++; } ll p=0,q=0,r=0,s=0; vector fx = compress(x); vector fy = compress(y); rep(i,0,n){ x[i]=bisect_left(fx,x[i]); y[i]=bisect_left(fy,y[i]); rt.add_point(x[i],y[i]); } rt.build(); r=(ll)n*(n-1)/2; s=(ll)n*(n-1)/2; for(auto[_,c]: cntx){ r-=(ll)c*(c-1)/2; } for(auto[_,c]: cnty){ s-=(ll)c*(c-1)/2; } const int INF=1e9; rep(i,0,n){ p+=rt.prod(x[i]+1,INF,y[i]+1,INF); p+=rt.prod(-INF,x[i],-INF,y[i]); q+=rt.prod(-INF,x[i],y[i]+1,INF); q+=rt.prod(x[i]+1,INF,-INF,y[i]); rt.set(x[i],y[i],1); } cout<