#region いつもの
using AtCoderProject;
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using static AtCoderProject.Global;
using BigInteger = System.Numerics.BigInteger;
using BitOperations = System.Numerics.BitOperations;
using IEnumerable = System.Collections.IEnumerable;
using IEnumerator = System.Collections.IEnumerator;
using StringBuilder = System.Text.StringBuilder;
using Unsafe = System.Runtime.CompilerServices.Unsafe;

namespace AtCoderProject { using System.IO; using System.Text; using System.Diagnostics; using System.Runtime.CompilerServices; public static class Global { public static T[] NewArray<T>(int len0, T value) => new T[len0].Fill(value); public static T[] NewArray<T>(int len0, Func<T> factory) { var arr = new T[len0]; for (int i = 0; i < arr.Length; i++) arr[i] = factory(); return arr; } public static T[][] NewArray<T>(int len0, int len1, T value) where T : struct { var arr = new T[len0][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, value); return arr; } public static T[][] NewArray<T>(int len0, int len1, Func<T> factory) { var arr = new T[len0][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, factory); return arr; } public static T[][][] NewArray<T>(int len0, int len1, int len2, T value) where T : struct { var arr = new T[len0][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, value); return arr; } public static T[][][] NewArray<T>(int len0, int len1, int len2, Func<T> factory) { var arr = new T[len0][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, factory); return arr; } public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, T value) where T : struct { var arr = new T[len0][][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, value); return arr; } public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, Func<T> factory) { var arr = new T[len0][][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, factory); return arr; } public static long Pow(long x, int y) { var res = 1L; for (; y > 0; y >>= 1) { if ((y & 1) == 1) res *= x; x *= x; } return res; } public static BigInteger ParseBigInteger(ReadOnlySpan<char> s) { /* 自前実装の方が速い */ BigInteger res; if (s.Length % 9 == 0) res = 0; else { res = new BigInteger(int.Parse(s.Slice(0, s.Length % 9))); s = s.Slice(s.Length % 9); } while (s.Length > 0) { var sp = s.Slice(0, 9); res *= 1000_000_000; res += int.Parse(sp); s = s.Slice(9); } return res; } public static int PopCount(int x) => BitOperations.PopCount((uint)x); public static int PopCount(long x) => BitOperations.PopCount((ulong)x); public static int PopCount(ulong x) => BitOperations.PopCount(x); public static int MSB(int x) => BitOperations.Log2((uint)x); public static int MSB(uint x) => BitOperations.Log2(x); public static int MSB(long x) => BitOperations.Log2((ulong)x); public static int MSB(ulong x) => BitOperations.Log2(x); public static int LSB(int x) => BitOperations.TrailingZeroCount((uint)x); public static int LSB(uint x) => BitOperations.TrailingZeroCount(x); public static int LSB(long x) => BitOperations.TrailingZeroCount((ulong)x); public static int LSB(ulong x) => BitOperations.TrailingZeroCount(x); } public static class Ext { public static bool UpdateMax(this ref int r, int val) { if (r < val) { r = val; return true; } return false; } public static bool UpdateMax(this ref long r, long val) { if (r < val) { r = val; return true; } return false; } public static bool UpdateMin(this ref int r, int val) { if (r > val) { r = val; return true; } return false; } public static bool UpdateMin(this ref long r, long val) { if (r > val) { r = val; return true; } return false; } public static long ToLong(this int i) => i; public static T[] Fill<T>(this T[] arr, T value) { Array.Fill(arr, value); return arr; } public static T[] Sort<T>(this T[] arr) { Array.Sort(arr); return arr; } public static string[] Sort(this string[] arr) => Sort(arr, StringComparer.OrdinalIgnoreCase); public static T[] Sort<T, U>(this T[] arr, Func<T, U> selector) where U : IComparable<U> => Sort(arr, (a, b) => selector(a).CompareTo(selector(b))); public static T[] Sort<T>(this T[] arr, Comparison<T> comparison) { Array.Sort(arr, comparison); return arr; } public static T[] Sort<T>(this T[] arr, IComparer<T> comparer) { Array.Sort(arr, comparer); return arr; } public static T[] Reverse<T>(this T[] arr) { Array.Reverse(arr); return arr; } public static (int index, T max) MaxBy<T>(this T[] arr) where T : IComparable<T> { T max = arr[0]; int maxIndex = 0; for (int i = 0; i < arr.Length; i++) { if (max.CompareTo(arr[i]) < 0) { max = arr[i]; maxIndex = i; } } return (maxIndex, max); } public static (TSource item, TMax max) MaxBy<TSource, TMax>(this IEnumerable<TSource> source, Func<TSource, TMax> maxBySelector) where TMax : IComparable<TMax> { TMax max; TSource maxByItem; var e = source.GetEnumerator(); e.MoveNext(); maxByItem = e.Current; max = maxBySelector(maxByItem); while (e.MoveNext()) { var item = e.Current; var next = maxBySelector(item); if (max.CompareTo(next) < 0) { max = next; maxByItem = item; } } return (maxByItem, max); } public static (int index, T min) MinBy<T>(this T[] arr) where T : IComparable<T> { T min = arr[0]; int minIndex = 0; for (int i = 0; i < arr.Length; i++) { if (min.CompareTo(arr[i]) > 0) { min = arr[i]; minIndex = i; } } return (minIndex, min); } public static (TSource item, TMin min) MinBy<TSource, TMin>(this IEnumerable<TSource> source, Func<TSource, TMin> minBySelector) where TMin : IComparable<TMin> { TMin min; TSource minByItem; var e = source.GetEnumerator(); e.MoveNext(); minByItem = e.Current; min = minBySelector(minByItem); while (e.MoveNext()) { var item = e.Current; var next = minBySelector(item); if (min.CompareTo(next) > 0) { min = next; minByItem = item; } } return (minByItem, min); } public static IComparer<T> Reverse<T>(this IComparer<T> comparer) => Comparer<T>.Create((x, y) => comparer.Compare(y, x)); public static Dictionary<TKey, int> GroupCount<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) => source.GroupBy(keySelector).ToDictionary(g => g.Key, g => g.Count()); public static Dictionary<TKey, int> GroupCount<TKey>(this IEnumerable<TKey> source) => source.GroupCount(i => i); public static ref T Get<T>(this T[] arr, int index) { if (index < 0) return ref arr[arr.Length + index]; return ref arr[index]; } public static TValue Get<TKey, TValue>(this Dictionary<TKey, TValue> dic, TKey key) { dic.TryGetValue(key, out var v); return v; } public static TValue GetOrInit<TKey, TValue>(this Dictionary<TKey, TValue> dic, TKey key, TValue value) { if (dic.TryGetValue(key, out var v)) return v; return dic[key] = value; } } public class ReverseComparer<T> : Comparer<T> where T : IComparable<T> { private static ReverseComparer<T> defaultComparer; public static new IComparer<T> Default => defaultComparer ??= new ReverseComparer<T>(); public override int Compare(T y, T x) => x.CompareTo(y); public override bool Equals(object obj) => obj != null && GetType() == obj.GetType(); public override int GetHashCode() => GetType().GetHashCode(); } public class ΔDebugView<T> { private IEnumerable<T> collection; public ΔDebugView(IEnumerable<T> collection) { this.collection = collection ?? throw new ArgumentNullException(nameof(collection)); }[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public T[] Items => collection.ToArray(); }[DebuggerStepThrough] public class ConsoleReader { const int BufSize = 1 << 12; private readonly byte[] buffer = new byte[BufSize]; private readonly Stream input; private readonly Encoding encoding; private int pos = 0; private int len = 0; public ConsoleReader(Stream input, Encoding encoding) { this.input = input; this.encoding = encoding; } public ConsoleReader(Stream input) : this(input, Console.InputEncoding) { } private void MoveNext() { if (++pos >= len) { len = input.Read(buffer, 0, buffer.Length); if (len == 0) { buffer[0] = 10; } pos = 0; } } public int Int { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { int res = 0; bool neg = false; while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); } do { res = checked(res * 10 + (buffer[pos] ^ 48)); MoveNext(); } while (48 <= buffer[pos]); return neg ? -res : res; } } public int Int0 => this.Int - 1; public long Long { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { long res = 0; bool neg = false; while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); } do { res = res * 10 + (buffer[pos] ^ 48); MoveNext(); } while (48 <= buffer[pos]); return neg ? -res : res; } } public long Long0 => this.Long - 1; public string String { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new List<byte>(); while (buffer[pos] <= 32) MoveNext(); do { sb.Add(buffer[pos]); MoveNext(); } while (32 < buffer[pos]); return this.encoding.GetString(sb.ToArray()); } } public string Ascii { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new StringBuilder(); while (buffer[pos] <= 32) MoveNext(); do { sb.Append((char)buffer[pos]); MoveNext(); } while (32 < buffer[pos]); return sb.ToString(); } } public string Line { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new List<byte>(); while (buffer[pos] <= 32) MoveNext(); do { sb.Add(buffer[pos]); MoveNext(); } while (buffer[pos] != 10 && buffer[pos] != 13); return this.encoding.GetString(sb.ToArray()); } } public char Char { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { while (buffer[pos] <= 32) MoveNext(); char res = (char)buffer[pos]; MoveNext(); return res; } } public double Double => double.Parse(this.Ascii);[DebuggerStepThrough] public struct RepeatReader { ConsoleReader cr; int count; public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; } public T[] Select<T>(Func<ConsoleReader, T> factory) { var arr = new T[count]; for (var i = 0; i < count; i++) arr[i] = factory(cr); return arr; } public T[] Select<T>(Func<ConsoleReader, int, T> factory) { var arr = new T[count]; for (var i = 0; i < count; i++) arr[i] = factory(cr, i); return arr; } public string[] Line { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Line; return arr; } } public string[] String { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.String; return arr; } } public string[] Ascii { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Ascii; return arr; } } public int[] Int { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int; return arr; } } public int[] Int0 { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int0; return arr; } } public long[] Long { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long; return arr; } } public long[] Long0 { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long0; return arr; } } public double[] Double { get { var arr = new double[count]; for (var i = 0; i < count; i++) arr[i] = cr.Double; return arr; } } public static implicit operator int[](RepeatReader rr) => rr.Int; public static implicit operator long[](RepeatReader rr) => rr.Long; public static implicit operator double[](RepeatReader rr) => rr.Double; public static implicit operator string[](RepeatReader rr) => rr.Ascii; } public RepeatReader Repeat(int count) => new RepeatReader(this, count);[DebuggerStepThrough] public struct SplitReader { ConsoleReader cr; public SplitReader(ConsoleReader cr) { this.cr = cr; } public string[] String { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.String); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public string[] Ascii { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Ascii); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public int[] Int { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public int[] Int0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public long[] Long { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public long[] Long0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public double[] Double { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<double>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Double); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public static implicit operator int[](SplitReader sr) => sr.Int; public static implicit operator long[](SplitReader sr) => sr.Long; public static implicit operator double[](SplitReader sr) => sr.Double; public static implicit operator string[](SplitReader sr) => sr.Ascii; } public SplitReader Split => new SplitReader(this); public static implicit operator int(ConsoleReader cr) => cr.Int; public static implicit operator long(ConsoleReader cr) => cr.Long; public static implicit operator double(ConsoleReader cr) => cr.Double; public static implicit operator string(ConsoleReader cr) => cr.Ascii; public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2) => (o1, o2) = (this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3) => (o1, o2, o3) = (this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4) => (o1, o2, o3, o4) = (this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5) => (o1, o2, o3, o4, o5) = (this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6) => (o1, o2, o3, o4, o5, o6) = (this, this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6, out ConsoleReader o7) => (o1, o2, o3, o4, o5, o6, o7) = (this, this, this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6, out ConsoleReader o7, out ConsoleReader o8) => (o1, o2, o3, o4, o5, o6, o7, o8) = (this, this, this, this, this, this, this, this); }[DebuggerStepThrough] public class ConsoleWriter { private readonly StreamWriter sw; public ConsoleWriter(Stream output) : this(output, Console.OutputEncoding) { } public ConsoleWriter(Stream output, Encoding encoding) { sw = new StreamWriter(output, encoding); } public void Flush() => sw.Flush(); public ConsoleWriter WriteLine(ReadOnlySpan<char> obj) { sw.WriteLine(obj); return this; } public ConsoleWriter WriteLine<T>(T obj) { sw.WriteLine(obj.ToString()); return this; } public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T> col) => WriteMany(' ', col); public ConsoleWriter WriteLineJoin<T>(IEnumerable<T> col) => WriteMany(' ', col); public ConsoleWriter WriteLines<T>(ReadOnlySpan<T> col) => WriteMany('\n', col); public ConsoleWriter WriteLines<T>(IEnumerable<T> col) => WriteMany('\n', col); public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>> cols) { var en = cols.GetEnumerator(); while (en.MoveNext()) WriteLineJoin(en.Current); return this; } private ConsoleWriter WriteMany<T>(char sep, ReadOnlySpan<T> col) { var en = col.GetEnumerator(); if (!en.MoveNext()) return this; sw.Write(en.Current.ToString()); while (en.MoveNext()) { sw.Write(sep); sw.Write(en.Current.ToString()); } sw.WriteLine(); return this; } private ConsoleWriter WriteMany<T>(char sep, IEnumerable<T> col) { var en = col.GetEnumerator(); if (!en.MoveNext()) return this; sw.Write(en.Current.ToString()); while (en.MoveNext()) { sw.Write(sep); sw.Write(en.Current.ToString()); } sw.WriteLine(); return this; } } }
public partial class Program {[System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)] public ConsoleReader cr;[System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)] public ConsoleWriter cw; public Program(ConsoleReader reader, ConsoleWriter writer) { this.cr = reader; this.cw = writer; System.Globalization.CultureInfo.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture; } static void Main() => new Program(new ConsoleReader(Console.OpenStandardInput()), new ConsoleWriter(Console.OpenStandardOutput())).Run(); public void Run() { var res = Calc(); if (res is double) cw.WriteLine(Result((double)res)); else if (res is bool) cw.WriteLine(Result((bool)res)); else if (res != null) cw.WriteLine(res.ToString()); cw.Flush(); } }
public partial class Program
{
    public static string Result(double d) => d.ToString("0.####################", System.Globalization.CultureInfo.InvariantCulture);
    #endregion
    public static string Result(bool b) => b ? "Yes" : "No";
    private object Calc()
    {
        N = cr;
        points = new Point[N];
        var xs = new int[N];
        var ys = new int[N];
        for (int i = 0; i < N; i++)
        {
            xs[i] = cr;
            ys[i] = cr;
        }
        xs = Compressed(xs);
        ys = Compressed(ys);
        bitL = new BinaryIndexedTree(N);
        bitR = new BinaryIndexedTree(N);
        for (int i = 0; i < N; i++)
        {
            points[i] = new Point(xs[i], ys[i]);
            bitR.Add(ys[i], 1);
        }
        points.Sort();

        foreach (var p in points)
            Calc(p);
        return res;
    }
    void Calc(Point p)
    {
        bitR.Add(p.y, -1);
        Mod hidariue, hidarishita, migiue, migishita;
        {
            int hidari = bitL.Sum(N);
            int migi = bitR.Sum(N);
            int hs = bitL.Sum(p.y);
            int ms = bitR.Sum(p.y);
            hidarishita = Mod.Pow(2, hs);
            migishita = Mod.Pow(2, ms);
            hidariue = Mod.Pow(2, hidari - hs);
            migiue = Mod.Pow(2, migi - ms);
        }
        res += Mod.Pow(2, N - 1);
        res += (hidarishita - 1) * (migiue - 1) * hidariue * migishita;
        res += (hidariue - 1) * (migishita - 1) * hidarishita * migiue;
        res -= (hidariue - 1) * (migishita - 1) * (hidarishita - 1) * (migiue - 1);
        bitL.Add(p.y, 1);
    }
    Mod.Factor factors = Mod.CreateFactor(1 + (int)1e5);
    Mod res;
    BinaryIndexedTree bitL;
    BinaryIndexedTree bitR;
    int N;
    Point[] points;
    static Dictionary<int, int> Compress(int[] orig) { var ox = new HashSet<int>(orig).ToArray().Sort(); var zip = new Dictionary<int, int>(); for (int i = 0; i < ox.Length; i++) zip[ox[i]] = i; return zip; }
    static int[] Compressed(int[] orig) { var res = new int[orig.Length]; var zip = Compress(orig); for (int i = 0; i < res.Length; i++) res[i] = zip[orig[i]]; return res; }
}

readonly struct Mod : IEquatable<Mod> { public const long mod = 998244353; public static readonly Mod invalid = new Mod(-1, false); public readonly long val; private Mod(long val, bool isValid) : this(val) { if (!isValid) this.val = val; } public Mod(long val) { this.val = val % mod; if (this.val < 0) this.val += mod; } public override bool Equals(object obj) => (obj is Mod) && this == ((Mod)obj); public bool Equals(Mod obj) => this.val == obj.val; public override int GetHashCode() => val.GetHashCode(); public override string ToString() => val.ToString(); public static implicit operator Mod(long x) => new Mod(x); public static implicit operator Mod(ConsoleReader cr) => new Mod(cr.Long); public static Mod operator -(Mod x) => new Mod(-x.val); public static Mod operator +(Mod x, Mod y) => new Mod(x.val + y.val); public static Mod operator -(Mod x, Mod y) => new Mod(x.val - y.val); public static Mod operator *(Mod x, Mod y) => new Mod(x.val * y.val); public static Mod operator /(Mod x, Mod y) => x * y.Inverse(); public static bool operator ==(Mod x, Mod y) => x.val == y.val; public static bool operator !=(Mod x, Mod y) => x.val != y.val; public Mod Inverse() { long a = val, b = mod, u = 1, v = 0; while (b > 0) { long t = a / b; var b2 = a - t * b; a = b; b = b2; var v2 = u - t * v; u = v; v = v2; } u %= mod; if (u < 0) u += mod; return u; } public static Mod Pow(Mod x, int y) { Mod res = 1; for (; y > 0; y >>= 1) { if ((y & 1) == 1) res *= x; x *= x; } return res; } public static Factor CreateFactor(int max) => new Factor(max); public class Factor { private readonly Mod[] fac, finv; public Factor(int max) { ++max; var inv = new Mod[max]; fac = new Mod[max]; finv = new Mod[max]; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (var i = 2; i < max; i++) { fac[i] = fac[i - 1] * i; inv[i] = mod - inv[mod % i].val * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i]; } } /** <summary>組み合わせ関数(二項係数)</summary> */ public Mod Combine(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * finv[k] * finv[n - k]; } public Mod Factorial(int n) => fac[n]; public Mod FactorialInvers(int n) => finv[n]; } }
static class ModExt { public static Mod Sum(this IEnumerable<Mod> source) { Mod sum = 0; foreach (var v in source) sum += v; return sum; } }

readonly struct Point : IEquatable<Point>, IComparable<Point>
{
    public readonly int x;
    public readonly int y;
    public Point(ConsoleReader cr) : this(cr, cr) { }
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    [System.ComponentModel.EditorBrowsable(System.ComponentModel.EditorBrowsableState.Never)]
    public void Deconstruct(out int v1, out int v2) { v1 = x; v2 = y; }
    public static implicit operator Point((int x, int y) tuple) => new Point(tuple.x, tuple.y);
    public double Distance(Point other) => Math.Sqrt(Distance2(other));
    private long Distance2(Point other)
    {
        var p = other - this;
        return (long)p.x * p.x + (long)p.y * p.y;
    }
    public long Inner(Point other) => (long)x * other.x + (long)y * other.y;
    public long Cross(Point other) => (long)x * other.y - (long)y * other.x;
    public static Point operator +(Point a, Point b) => new Point(a.x + b.x, a.y + b.y);
    public static Point operator -(Point a, Point b) => new Point(a.x - b.x, a.y - b.y);
    public int CompareTo(Point other)
    {
        var xd = this.x.CompareTo(other.x);
        if (xd != 0) return xd;
        return this.y.CompareTo(other.y);
    }

    public bool Equals(Point other) => this.x == other.x && this.y == other.y;
    public override bool Equals(object obj) => obj is Point && Equals((Point)obj);
    public override int GetHashCode() => HashCode.Combine(x, y);
    public override string ToString() => $"({x}, {y})";
}


[System.Diagnostics.DebuggerTypeProxy(typeof(BinaryIndexedTreeDebugView))]
class BinaryIndexedTree
{
    private int Operate(int v, int w) => v + w;
    public void Add(int i, int w)
    {
        for (++i; i < tree.Length; i += (i & -i))
            tree[i] = Operate(tree[i], w);
    }
    public int Sum(int toExclusive)
    {
        int res = 0;
        for (var i = toExclusive; i > 0; i -= (i & -i))
            res = Operate(res, tree[i]);
        return res;
    }

    public int Sum(int from, int toExclusive) => Sum(toExclusive) - Sum(from);
    public int LowerBound(int w)
    {
        if (w <= 0) return 0;
        int x = 0;
        for (int k = 1 << MSB(tree.Length - 1); k > 0; k >>= 1)
        {
            var nx = x + k;
            if (nx < tree.Length && tree[nx] < w)
            {
                x = nx;
                w -= tree[nx];
            }
        }
        return x;
    }

    private int[] tree;
    public int Length => tree.Length - 1;
    public int Slice(int from, int length) => Sum(from, from + length);

    public BinaryIndexedTree(int size)
    {
        tree = new int[size + 1];
    }
    public BinaryIndexedTree(int[] initArray) : this(initArray.Length)
    {
        Array.Copy(initArray, 0, tree, 1, initArray.Length);
        for (int i = 1; i < tree.Length; i++)
        {
            var ni = i + (i & -i);
            if (ni < tree.Length)
                tree[ni] = Operate(tree[i], tree[ni]);
        }
    }

    public class BinaryIndexedTreeDebugView
    {
        private BinaryIndexedTree bit;
        public BinaryIndexedTreeDebugView(BinaryIndexedTree bit)
        {
            this.bit = bit;
        }

        [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)]
        public string[] Tree
        {
            get
            {
                var res = new string[bit.tree.Length - 1];
                for (var i = 0; i < res.Length; i++)
                {
                    res[i] = $"data:{bit.tree[i + 1]} single:{bit.Sum(i, i + 1)}";
                }
                return res;
            }
        }
    }
}


Measured memory_bytes: 48892