#954398 (C#) No.2650 [Cherry 6th Tune *] セイジャク

• 問題: No.2650 [Cherry 6th Tune *] セイジャク
• ユーザー: crimsontea
• 提出日時: 2024-02-23 22:08:47
• 言語: C# (.NET 8.0.203)
• 結果: AC
• 実行時間: 1,369 ms / 2,500 ms
• コード長: 25,562 bytes
• コンパイル時間: 8,635 ms
• コンパイル使用メモリ: 158,988 KB
• 実行使用メモリ: 226,680 KB
• 最終ジャッジ日時: 2024-02-23 22:09:32
• 合計ジャッジ時間: 31,174 ms
• ジャッジサーバーID （参考情報）: judge16 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	91 ms; 33,572 KB
testcase_01	AC	91 ms; 33,572 KB
testcase_02	AC	318 ms; 61,988 KB
testcase_03	AC	116 ms; 40,356 KB
testcase_04	AC	272 ms; 63,012 KB
testcase_05	AC	281 ms; 62,884 KB
testcase_06	AC	168 ms; 50,980 KB
testcase_07	AC	226 ms; 62,500 KB
testcase_08	AC	174 ms; 49,700 KB
testcase_09	AC	600 ms; 78,452 KB
testcase_10	AC	531 ms; 79,216 KB
testcase_11	AC	584 ms; 78,548 KB
testcase_12	AC	586 ms; 78,288 KB
testcase_13	AC	592 ms; 79,080 KB
testcase_14	AC	557 ms; 78,704 KB
testcase_15	AC	639 ms; 78,900 KB
testcase_16	AC	802 ms; 75,716 KB
testcase_17	AC	801 ms; 75,556 KB
testcase_18	AC	812 ms; 75,616 KB
testcase_19	AC	808 ms; 75,620 KB
testcase_20	AC	825 ms; 75,880 KB
testcase_21	AC	850 ms; 75,880 KB
testcase_22	AC	819 ms; 75,744 KB
testcase_23	AC	795 ms; 75,880 KB
testcase_24	AC	799 ms; 75,880 KB
testcase_25	AC	768 ms; 75,964 KB
testcase_26	AC	824 ms; 76,016 KB
testcase_27	AC	794 ms; 75,760 KB
testcase_28	AC	789 ms; 75,728 KB
testcase_29	AC	805 ms; 75,868 KB
testcase_30	AC	1,369 ms; 76,124 KB
testcase_31	AC	773 ms; 77,424 KB
testcase_32	AC	575 ms; 226,680 KB

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (107 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
/home/judge/data/code/Main.cs(343,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(344,30): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(118,39): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.0/publish/

ソースコード

using A;
using AtCoder.Extension;
using System;
using System.Buffers;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using static A.InputUtility;
class Program
{
    static void Main()
    {
        using Output output = new(false);

        InputNewLine();
        var (n, a) = (NextInt32, NextInt32);
        InputNewLine();
        var x = GetInt32Array();

        InputNewLine();
        var t = NextInt32;

        var query = new (int l, int r)[t];
        for (int i = 0; i < query.Length; i++)
        {
            InputNewLine();
            query[i] = (NextInt32, NextInt32);
        }

        SortedMultiset<Data> set = new();
        for (int i = 0; i < x.Length; i++)
        {
            set.Add(new Data(x[i], i));
        }

        int[] res = Enumerable.Repeat(-1, n).ToArray();

        for (int i = query.Length - 1; i >= 0; i--)
        {
            var (l, r) = query[i];
            var first = set.IndexOf(new Data(l, 0));
            var last = set.LastIndexOf(new Data(r, 0));

            if(first == last)
            {
                continue;
            }

            List<Data> list = new();    

            for (int k = first; k < last; k++)
            {
                var (p, index) = set[k];
                res[index] = i + 1;

                list.Add(new Data(p, index));
            }

            foreach (var item in list)
            {
                set.Discard(item);
            }
        }

        Console.WriteLine(string.Join('\n', res));
    }

    public record struct Data(int X, int Index) : IComparable<Data>
    {
        int IComparable<Data>.CompareTo(Data other) => X.CompareTo(other.X);
    }
}

public class SortedMultiset<T> where T : struct, IComparable<T>
{
    private const int BUCKET_RATIO = 16;
    private const int SPLIT_RATIO = 24;

    private List<List<T>> _a;
    private int _size;
    public SortedMultiset()
    {
        _a = new List<List<T>>(0);
    }

    public SortedMultiset(IEnumerable<T> enumerable)
    {
        // Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)
        var a = enumerable.ToArray();
        _size = a.Length;
        for (int i = 1; i < a.Length; i++)
        {
            if (a[i - 1].CompareTo(a[i]) > 0)
            {
                Array.Sort(a);
                break;
            }
        }

        int bucketSize = (int)Math.Ceiling(Math.Sqrt(_size / (double)BUCKET_RATIO));
        _a = a.Chunk(bucketSize).Select(x => x.ToList()).ToList();
    }

    public IEnumerable<T> AsEnumerable()
    {
        foreach (var i in _a)
            foreach (var j in i) yield return j;
    }

    public IEnumerable<T> AsReversedEnumerable()
    {
        foreach (IEnumerable<T> i in ((IEnumerable<List<T>>)_a).Reverse())
            foreach (var j in i.Reverse()) yield return j;
    }

    public override bool Equals(object? obj)
    {
        if (obj is SortedMultiset<T> set)
        {
            return AsEnumerable().SequenceEqual(set.AsEnumerable());
        }
        return false;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(AsEnumerable());
    }

    public int Count => _size;

    public override string ToString()
    {
        return string.Join(", ", AsEnumerable());
    }

    private (List<T>, int, int) Position(T x)
    {
        // return the bucket, index of the bucket and position in which x should be. this must not be empty.
        for (int i = 0; i < _a.Count; i++)
        {
            var bucket = _a[i];
            if (x.CompareTo(bucket[bucket.Count - 1]) <= 0)
            {
                return (bucket, i, bucket.BinarySearch(x));
            }
        }

        return (_a[^1], _a.Count - 1, _a[^1].Count);
    }

    public bool Contains(T x)
    {
        if (_size == 0) return false;
        var (_, _, index) = Position(x);
        return index >= 0;
    }

    public int CountOf(T x)
    {
        // Count the number of x.
        return LastIndexOf(x) - IndexOf(x);
    }

    public void Add(T x)
    {
        // Add an element. / O(√N)
        if (_size == 0)
        {
            _a = new List<List<T>>() { new() { x } };
            _size = 1;
            return;
        }
        var (bucket, bucketIndex, index) = Position(x);
        if (index < 0) index = ~index;
        bucket.Insert(index, x);
        _size++;
        if (bucket.Count > _a.Count * SPLIT_RATIO)
        {
            int mid = bucket.Count / 2;
            _a[bucketIndex] = bucket.GetRange(0, mid);
            _a.Insert(bucketIndex + 1, bucket.GetRange(mid, bucket.Count - mid));
        }
    }

    private T Pop(List<T> bucket, int bucketIndex, int index)
    {
        var ans = bucket[index];
        bucket.RemoveAt(index);
        _size--;
        if (bucket.Count == 0) _a.RemoveAt(bucketIndex);
        return ans;
    }

    public bool Discard(T x)
    {
        // Remove an element and return True if removed. / O(√N)
        if (_size == 0) return false;
        var (bucket, bucketIndex, index) = Position(x);
        if (index < 0) return false;
        Pop(bucket, bucketIndex, index);
        return true;
    }

    public T Lt(T x)
    {
        // Find the largest element < x, or default(T) if it doesn't exist.
        foreach (var bucket in ((IEnumerable<List<T>>)_a).Reverse())
        {
            if (bucket[0].CompareTo(x) < 0)
            {
                return bucket[bucket.BinarySearch(x) - 1];
            }
        }
        return default;
    }

    public T Le(T x)
    {
        // Find the largest element <= x, or default(T) if it doesn't exist.
        foreach (var bucket in ((IEnumerable<List<T>>)_a).Reverse())
        {
            if (bucket[0].CompareTo(x) <= 0)
            {
                var index = bucket.BinarySearch(x);
                if (index < 0) index = ~index;
                return bucket[index - 1];
            }
        }
        return default;
    }

    public T Gt(T x)
    {
        // Find the smallest element > x, or default(T) if it doesn't exist.
        foreach (var bucket in _a)
        {
            if (bucket[bucket.Count - 1].CompareTo(x) > 0)
            {
                var index = bucket.BinarySearch(x);
                if (index < 0) index = ~index;
                return bucket[index];
            }
        }
        return default;
    }

    public T Ge(T x)
    {
        // Find the smallest element >= x, or default(T) if it doesn't exist.
        foreach (var bucket in _a)
        {
            if (bucket[bucket.Count - 1].CompareTo(x) >= 0)
            {
                var index = bucket.BinarySearch(x);
                if (index < 0) index = ~index;
                return bucket[index];
            }
        }
        return default;
    }

    public T this[int i]
    {
        // Return the i-th element.
        get
        {
            if (i < 0)
                throw new IndexOutOfRangeException();

            foreach (var bucket in _a)
            {
                if (i < bucket.Count) return bucket[i];
                i -= bucket.Count;
            }

            throw new IndexOutOfRangeException();
        }
    }


    public T Pop(int i)
    {
        // Pop and return the i-th element.
        if (i < 0)
            throw new IndexOutOfRangeException();

        for (int b = 0; b < _a.Count; b++)
        {
            var bucket = _a[b];
            if (i < bucket.Count) return Pop(bucket, b, i);
            i -= bucket.Count;
        }

        throw new IndexOutOfRangeException();
    }

    public T Pop() => Pop(_size - 1);
    public T Pop(Index index) => Pop(index.GetOffset(_size));

    public int IndexOf(T x)
    {
        // Count the number of elements < x.
        int ans = 0;
        foreach (var bucket in _a)
        {
            if (bucket[^1].CompareTo(x) >= 0)
            {
                var index = bucket.LowerBound(x);
                //if (index < 0) index = ~index;
                return ans + index;
            }
            ans += bucket.Count;
        }
        return ans;
    }

    public int LastIndexOf(T x)
    {
        // Count the number of elements <= x.
        int ans = 0;
        foreach (var bucket in _a)
        {
            if (bucket[^1].CompareTo(x) > 0)
            {
                var index = bucket.UpperBound(x);
                //if (index < 0) index = ~index;
                return ans + index;
            }
            ans += bucket.Count;
        }
        return ans;
    }
}


namespace A
{
    public static class InputUtility
    {
        private static string[]? s_inputs;
        private static string? s_raw;
        private static int s_index = 0;

        private static void Init() => s_index = 0;
        public static int NextInt32 => int.Parse(s_inputs![s_index++]!);
        public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!);
        public static long NextInt64 => long.Parse(s_inputs![s_index++]!);
        public static ulong NextUInt64 => ulong.Parse(s_inputs![s_index++]!);
        public static string NextString => s_inputs![s_index++];
        public static char NextChar => s_inputs![s_index++][0];
        public static decimal NextDecimal => decimal.Parse(s_inputs![s_index++]!);
        public static BigInteger NextBigInteger => BigInteger.Parse(s_inputs![s_index++]!);
        public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray();
        public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray();
        public static string GetRawString() => s_raw!;
#if DEBUG
        private static TextReader? s_textReader;
        public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));
#endif
        public static bool InputNewLine()
        {
#if DEBUG
            if (s_textReader is TextReader sr)
            {
                Init();
                s_raw = sr.ReadLine()!;
                s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
                return true;
            }
#endif
            Init();
            s_raw = Console.ReadLine()!;
            s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
            return true;
        }
    }

    public static class CombinationFunction
    {
        public static void PartedRotate<T>(T[] a, int first1, int last1, int first2, int last2)
        {
            if (first1 == last1 || first2 == last2) return;
            int next = first2;
            while (first1 != next)
            {
                Swap(a, first1++, next++);
                if (first1 == last1) first1 = first2;
                if (next == last2)
                {
                    next = first2;
                }
                else if (first1 == first2)
                {
                    first2 = next;
                }
            }
        }

        public static bool NextCombinationImp<T>(T[] a, int first1, int last1, int first2, int last2) where T : IComparable<T>
        {
            if (first1 == last1 || first2 == last2) return false;
            int target = last1 - 1;
            int lastElem = last2 - 1;

            while (target != first1 && !(a[target].CompareTo(a[lastElem]) < 0)) target--;
            if (target == first1 && !(a[target].CompareTo(a[lastElem]) < 0))
            {
                PartedRotate(a, first1, last1, first2, last2);
                return false;
            }

            int next = first2;
            while (!(a[target].CompareTo(a[next]) < 0)) next++;
            Swap(a, target++, next++);
            PartedRotate(a, target, last1, next, last2);
            return true;
        }

        public static bool NextCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>
            => NextCombinationImp(a, first, mid, mid, last);

        public static bool PrevCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>
            => NextCombinationImp(a, mid, last, first, mid);

        public static void Swap<T>(T[] a, int i, int j) => (a[i], a[j]) = (a[j], a[i]);
    }

    public static class PermutationFunction
    {
        public static bool NextPermutation<T>(T[] a) where T : IComparable<T>
        {
            int n = a.Length;

            int i = n - 2;
            while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; }

            if (i < 0) { return false; }

            int j = n - 1;
            while (a[j].CompareTo(a[i]) <= 0) { j--; }
            (a[i], a[j]) = (a[j], a[i]);

            Array.Reverse(a, i + 1, n - i - 1);

            return true;
        }
    }

    public readonly struct Output : IDisposable
    {
        private readonly StreamWriter _sw;
#if DEBUG
        public Output(string path)
        {
            var fs = new FileStream(path, FileMode.Create, FileAccess.Write);
            _sw = new StreamWriter(fs);
            Console.SetOut(_sw);
        }
#endif
        public Output(bool autoFlush)
        {
            _sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush };
            Console.SetOut(_sw);
        }

        public void Dispose()
        {
            _sw.Dispose();
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal void Flush()
        {
            _sw.Flush();
        }
    }

    public static class ArrayExtensions
    {
        public static void Swap<T>(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]);

        public static int LowerBound<T>(this T[] a, T target) where T : IComparable<T>
        {
            int ok = a.Length;
            int ng = -1;

            while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)
                (ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid);

            return ok;
        }

        public static int UpperBound<T>(this T[] a, T target) where T : IComparable<T>
        {
            int ok = a.Length;
            int ng = -1;

            while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)
                (ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid);

            return ok;
        }

        public struct IndexedEnumerable<T> : IEnumerable<(T item, int index)>
        {
            private readonly T[] _a;
            private readonly int _startIndex;

            public IndexedEnumerable(T[] a, int startIndex = 0)
            {
                _a = a;
                _startIndex = startIndex;
            }

            public readonly IndexedEnumerator<T> GetEnumerator() => new IndexedEnumerator<T>(_a, _startIndex);
            IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
            IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator();
        }

        public struct IndexedEnumerator<T> : IEnumerator<(T item, int index)>
        {
            public readonly (T item, int index) Current => (_a[_index], _index + _startIndex);

            private int _index;
            private int _startIndex;
            private T[] _a;

            public IndexedEnumerator(T[] a, int startIndex)
            {
                _index = -1;
                _a = a;
                _startIndex = startIndex;
            }

            public bool MoveNext() => ++_index < _a.Length;
            readonly object IEnumerator.Current => Current;
            public readonly void Dispose() { }
            public void Reset() => _index = -1;
        }

        /// <returns>(T value, int index)</returns>
        public static IndexedEnumerable<T> Enumerate<T>(this T[] arr, int startIndex = 0) => new IndexedEnumerable<T>(arr, startIndex);
    }

    public static class IEnumerableExtensions
    {
        public static IEnumerable<TSource> Log<TSource>(this IEnumerable<TSource> source)
        {
            Console.WriteLine(string.Join(' ', source));
            return source;
        }

        public static ScanEnumerable<TSource, TAccumulate> Scan<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed,
        Func<TAccumulate, TSource, TAccumulate> accumulator) where TSource : struct where TAccumulate : struct
        {
            return new ScanEnumerable<TSource, TAccumulate>(source, accumulator, seed);
        }

        public static IEnumerable<TAccumulate> ScanExSeed<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed,
            Func<TAccumulate, TSource, TAccumulate> accumulator)
        {
            var accumulation = new List<TAccumulate>();

            var current = seed;
            foreach (var item in source)
            {
                current = accumulator(current, item);
                accumulation.Add(current);
            }

            return accumulation;
        }

        public readonly struct ScanEnumerable<TSource, TAccumulate> : IEnumerable<TAccumulate> where TSource : struct where TAccumulate : struct
        {
            private readonly IEnumerable<TSource> _source;
            private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;
            private readonly TAccumulate _seed;

            public ScanEnumerable(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed)
            {
                _source = source;
                _accumulator = accumulator;
                _seed = seed;
            }

            public readonly ScanEnumerator<TSource, TAccumulate> GetEnumerator() => new(_source, _accumulator, _seed);
            readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
            readonly IEnumerator<TAccumulate> IEnumerable<TAccumulate>.GetEnumerator() => GetEnumerator();
        }

        public struct ScanEnumerator<TSource, TAccumulate> : IEnumerator<TAccumulate> where TSource : struct where TAccumulate : struct
        {
            private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;

            private readonly IEnumerator<TSource> _enumerator;
            private TAccumulate _current;

            private bool _secondOrLaterElement = false;

            public ScanEnumerator(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed)
            {
                _enumerator = source.GetEnumerator();
                _accumulator = accumulator;

                _current = seed;
            }

            public readonly TAccumulate Current => _current;
            readonly object IEnumerator.Current => Current;

            public readonly void Dispose() { }

            public bool MoveNext()
            {
                if (_secondOrLaterElement)
                {
                    if (_enumerator.MoveNext())
                    {
                        _current = _accumulator(_current, _enumerator.Current);
                        return true;
                    }
                    return false;
                }
                else
                {
                    _secondOrLaterElement = true;
                    return true;
                }
            }

            public void Reset()
            {
                throw new NotSupportedException();
            }
        }

        public static IEnumerable<TSource> Scan<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, TSource, TSource> accumulator)
        {
            if (source is null)
                throw new ArgumentNullException(paramName: nameof(source));

            if (accumulator is null)
                throw new ArgumentNullException(paramName: nameof(accumulator));

            var accumulation = new List<TSource>();

            if (source.Any() is false)
            {
                return accumulation;
            }

            var current = source.First();
            accumulation.Add(current);

            foreach (var item in source.Skip(1))
            {
                current = accumulator(current, item);
                accumulation.Add(current);
            }

            return accumulation;
        }

        public static CombinationEnumerable<T> Combination<T>(this T[] a, int k) where T : IComparable<T>
            => new(a, k);

        public readonly struct CombinationEnumerable<T> where T : IComparable<T>
        {
            private readonly T[] _a;
            private readonly int _k;

            public CombinationEnumerable(T[] a, int k)
            {
                _a = a;
                _k = k;
            }

            public readonly CombinationEnumerator<T> GetEnumerator() => new(_a, _k);
        }

        public struct CombinationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>
        {
            private readonly int _k;
            private readonly T[] _a;
            private readonly int _n;
            private bool _secondOrLaterElement = false;

            public CombinationEnumerator(T[] a, int k)
            {
                _a = a;
                _n = a.Length;
                _k = k;
            }

            public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[.._k];
            readonly object IEnumerator.Current => Current;

            public readonly void Dispose() { }

            public bool MoveNext()
            {
                if (_secondOrLaterElement)
                {
                    return CombinationFunction.NextCombination(_a, 0, _k, _n);
                }
                else
                {
                    _secondOrLaterElement = true;
                    return true;
                }
            }

            public void Reset()
            {
                throw new NotSupportedException();
            }
        }

        public static PermutationEnumerable<T> Permutation<T>(this T[] a) where T : IComparable<T> => new(a);

        public readonly struct PermutationEnumerable<T> where T : IComparable<T>
        {
            private readonly T[] _a;
            public PermutationEnumerable(T[] a) => _a = a;
            public readonly PermutationEnumerator<T> GetEnumerator() => new(_a);
        }

        public struct PermutationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>
        {
            private readonly T[] _a;
            private readonly int _n;
            private bool _secondOrLaterElement = false;

            public PermutationEnumerator(T[] a)
            {
                _a = a;
                _n = a.Length;
            }
            public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[..];
            readonly object IEnumerator.Current => Current;

            public readonly void Dispose() { }

            public bool MoveNext()
            {
                if (_secondOrLaterElement)
                {
                    return PermutationFunction.NextPermutation(_a);
                }
                else
                {
                    _secondOrLaterElement = true;
                    return true;
                }
            }

            public void Reset() => throw new NotSupportedException();
        }
    }

    public class MyMath
    {
        public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x);
        public static long Pow10(int y) => Pow(10, y);
        public static long Pow2(int y) => Pow(2, y);
    }

    public class MyMathBigInteger
    {
        public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x);
        public static BigInteger Pow10(int y) => Pow(10, y);
        public static BigInteger Pow2(int y) => Pow(2, y);
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder.Extension{public static class BinarySearchListExtension{[MethodImpl(256)]public static int LowerBound<T,TOp>(this IList<T>a,T v,TOp cmp)where TOp:IComparer<T> =>LowerBound(a,new CmpWrapper<T,TOp>(v,cmp));[MethodImpl(256)]public static int LowerBound<T,TCv>(this IList<T>a,TCv v)where TCv:IComparable<T> =>BinarySearch<T,TCv,L>(a,v);[MethodImpl(256)]public static int UpperBound<T,TOp>(this IList<T>a,T v,TOp cmp)where TOp:IComparer<T> =>UpperBound(a,new CmpWrapper<T,TOp>(v,cmp));[MethodImpl(256)]public static int UpperBound<T,TCv>(this IList<T>a,TCv v)where TCv:IComparable<T> =>BinarySearch<T,TCv,U>(a,v);private readonly struct CmpWrapper<T,TCmp>:IComparable<T>where TCmp:IComparer<T>{readonly T v;readonly TCmp cmp;public CmpWrapper(T v,TCmp cmp){this.v=v;this.cmp=cmp;}[MethodImpl(256)]public int CompareTo(T other)=>cmp.Compare(v,other);}private interface IOk{bool Ok(int c);}private struct L:IOk{[MethodImpl(256)]public bool Ok(int c)=>c<=0;}private struct U:IOk{[MethodImpl(256)]public bool Ok(int c)=>c<0;}[MethodImpl(256)]private static int BinarySearch<T,TCv,TOk>(this IList<T>a,TCv v)where TCv:IComparable<T>where TOk:IOk{int ok=a.Count;int ng=-1;while(ok-ng>1){var m=(ok+ng)>>1;var c=v.CompareTo(a[m]);if(default(TOk).Ok(c))ok=m;else ng=m;}return ok;}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander