超级函数库（1.8.3版本）

上个版本依旧是有许多BUG，这次我也是连喝了3瓶魔爪来DeBug和叫我兄弟@DeepSeek来一起修，并且这次我连续问了好几次我兄弟@DeepSeek这个函数库有没有BUG，截图证明：

// 1.8.3版本：修复全部P0、P1级的BUG，大部分P2级的BUG
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512er,sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,bmi,bmi2,lzcnt")
extern "C" long read(int, void *, unsigned long);
extern "C" long write(int, const void *, unsigned long);
typedef long long ll;
typedef long long ssize_t;
typedef unsigned long long ull;
typedef unsigned long long size_t;
typedef double lf;
typedef __builtin_va_list va_list;
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define fnlikely(cond) __builtin_unpredictable((cond))
#define memcpy(r1, s, len) __builtin_memcpy((r1), (s), (len))
#define memmove(r1, s ,len) __builtin_memmove((r1), (s), (len))
#define strlen(r1) __builtin_strlen((r1))
#define memcmp(s1, s2, n) __builtin_memcmp((s1), (s2), (n))
#define strcmp(s1, s2) __builtin_strcmp((s1), (s2))
#define strstr(s1, s2) __builtin_strstr((s1), (s2))
#define abs(x) __builtin_llabs(x)
#define sin(x) __builtin_sin((x))
#define cos(x) __builtin_cos((x))
#define clz(x) __builtin_clz((x))
#define clzll(x) __builtin_clzll((x))
#define ctz(x) __builtin_ctz((x))
#define ctzll(x) __builtin_ctzll((x))
#define ffs(x) __builtin_ffs((x))
#define parity(x) __builtin_parity((x))
#define ceil(x) __builtin_ceil((x))
#define floor(x) __builtin_floor((x))
#define round(x) __builtin_round((x))
#define roundll(x) __builtin_roundll((x))
#define exp(x) __builtin_exp((x))
#define exp2(x) __builtin_exp2((x))
#define acos(x) __builtin_acos((x))
#define types_compatible_p(type1, type2) __builtin_types_compatible_p((type1), (type2))
#define constant_p(expr) __builtin_constant_p((expr))
#define assume(cond) __builtin_assume((cond))
#define unreachable() __builtin_unreachable()
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))
#define add_overflow(x, y, result) __builtin_add_overflow((x), (y), (&result))
#define mul_overflow(x, y, result) __builtin_mul_overflow((x), (y), (&result))
#define bswap16(x) __builtin_bswap16((x))
#define bswap32(x) __builtin_bswap32((x))
#define bswap64(x) __builtin_bswap64((x))
#define assume_aligned(ptr, align) __builtin_assume_aligned((ptr), (align))
#define prefetch(a,b,c) __builtin_prefetch(a,b,c)
#define ln(x) __builtin_log((x))
#define log2(x) __builtin_log2((x))
#define pow(a,b) __builtin_pow((a),(b))
#define va_arg(a,b) __builtin_va_arg(a,b)
#define va_start(ap, last) __builtin_va_start((ap), (last))
#define va_end(ap)         __builtin_va_end((ap))
#define va_copy(dest, src) __builtin_va_copy((dest), (src))
#define EOF (-1)
#define elif else if
#define LLONG_MAX 9223372036854775807LL
#define ULLONG_MAX 18446744073709551615ULL
#define LLONG_MIN (-9223372036854775807LL-1LL)
#define INT_MAX 2147483647
#define INT_MIN (-2147483647-1)
#define UINT_MAX 4294967295U
#define NAN __builtin_nan("0x7fc00000")
template <typename T>
__attribute__((always_inline))
inline T max(T a,T b){return a>b?a:b;}
template <typename T>
__attribute__((always_inline))
inline T min(T a,T b){return a<b?a:b;}
static const lf pi = acos(-1.0), e = exp(1.0);
inline lf log(lf x,lf n){if(n==2)return log2(x);if(n==e)return ln(x);return ln(x) / ln(n);}
static char _rbuf[1 << 16] __attribute__((aligned(64)));
static char* _rptr = _rbuf;static char* _rend = _rbuf;
__attribute__((always_inline))
static inline int _gc() {
    if (_rptr == _rend) {
        ssize_t n=read(0,_rbuf,sizeof(_rbuf));
        if(n<1)return EOF;
        _rptr=_rbuf,_rend=_rbuf+n;
    }
    return static_cast<unsigned char>(*_rptr++);
}
static char _wbuf[1 << 16] __attribute__((aligned(64)));
static char* _wptr = _wbuf;
__attribute__((always_inline))
static inline void _return() {
    if (_wptr == _wbuf) return;
    char* p = _wbuf;
    size_t remaining = _wptr - _wbuf;
    while (remaining > 0) {
        ssize_t n = write(1, p, remaining);
        if (n <= 0) break;
        p += n,remaining -= n;
    }
    _wptr = _wbuf;
}
__attribute__((always_inline))
static inline void _pc(char c) {
    if (unlikely(_wptr == _wbuf + sizeof(_wbuf))) _return();
    *_wptr++ = c;
}
namespace std {
template<typename T>
struct remove_reference { using type = T; };
template<typename T>
struct remove_reference<T&> { using type = T; };
template<typename T>
struct remove_reference<T&&> { using type = T; };
template<typename T>
using remove_reference_t = typename remove_reference<T>::type;
template<typename T>
constexpr remove_reference_t<T>&& move(T&& t) noexcept {return static_cast<remove_reference_t<T>&&>(t);}
template<typename T>
constexpr T&& forward(remove_reference_t<T>& t) noexcept {return static_cast<T&&>(t);}
template<typename T>
constexpr T&& forward(remove_reference_t<T>&& t) noexcept {return static_cast<T&&>(t);}
template<typename R1, typename R2>
struct tie_type {R1& first;R2& second;};
template<typename R1, typename R2>
constexpr tie_type<R1, R2> tie(R1& a, R2& b) {return tie_type<R1, R2>{a, b};}
template <typename T>
__attribute__((always_inline))
inline void swap(T& a, T& b) {T t = move(a); a = move(b); b = move(t);}
template<typename T1, typename T2>
struct pair {
    T1 first;
    T2 second;
    constexpr pair() : first(), second() {}
    template<typename U1, typename U2>
    constexpr pair(U1&& a, U2&& b): first(forward<U1>(a)), second(forward<U2>(b)) {}
    constexpr pair(const pair& other): first(other.first), second(other.second) {}
    pair(pair&& other) noexcept: first(move(other.first)), second(move(other.second)) {}
    pair& operator=(const pair& other) {if (this != &other) {first = other.first;second = other.second;}return *this;}
    pair& operator=(pair&& other) noexcept {
        if (this != &other) {
            first = move(other.first);
            second = move(other.second);
        }
        return *this;
    }
    template<typename R1, typename R2>
    pair& operator=(const tie_type<R1, R2>& t) {first = t.first;second = t.second;return *this;}
    constexpr bool operator==(const pair& other) const {return first == other.first && second == other.second;}
    constexpr bool operator!=(const pair& other) const {return !(*this == other);}
    constexpr bool operator<(const pair& other) const {return first < other.first || (!(other.first < first) && second < other.second);}
};
template<typename T1, typename T2>
constexpr pair<remove_reference_t<T1>, remove_reference_t<T2>>
make_pair(T1&& a, T2&& b) {return pair<remove_reference_t<T1>, remove_reference_t<T2>>(forward<T1>(a), forward<T2>(b));}
template<typename T>
struct vector {
    T* data;
    size_t sz,cap;
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin() { return data; }
    iterator end() { return data + sz; }
    const_iterator begin() const { return data; }
    const_iterator end() const { return data + sz; }
    vector() : data(nullptr), sz(0), cap(0) {}
    explicit vector(size_t n) : data(new T[n]), sz(n), cap(n) { for (size_t i = 0; i < n; i++) data[i] = T(); }
    vector(size_t n, const T& value) : data(new T[n]), sz(n), cap(n) { for (size_t i = 0; i < n; i++) data[i] = value; }
    vector(const vector& other) : data(new T[other.cap]), sz(other.sz), cap(other.cap) { for (size_t i = 0; i < sz; i++) data[i] = other.data[i]; }
    vector(vector&& other) noexcept : data(other.data), sz(other.sz), cap(other.cap) {other.data = nullptr;other.sz = other.cap = 0;}
    vector& operator=(const vector& other) {
        if (this != &other) {
            delete[] data;
            cap = other.cap;
            sz = other.sz;
            data = new T[cap];
            for (size_t i = 0; i < sz; i++) data[i] = other.data[i];
        }
        return *this;
    }
    vector& operator=(vector&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;sz = other.sz;cap = other.cap;
            other.data = nullptr;other.cap = other.sz = 0;
        }
        return *this;
    }
    ~vector() { delete[] data; }
    void push_back(const T& value) {
        if (sz == cap) {size_t new_cap = (cap == 0) ? 1 : cap * 2;reserve(new_cap);}
        data[sz++] = value;
    }
    void push_back(T&& value) {
        if (sz == cap) {size_t new_cap = (cap == 0) ? 1 : cap * 2;reserve(new_cap);}
        data[sz++] = move(value);
    }
    void pop_back() { if (sz > 0) sz--; }
    void reserve(size_t new_cap) {
        if (new_cap <= cap) return;
        T* new_data = new T[new_cap];
        for (size_t i = 0; i < sz; i++) new_data[i] = move(data[i]);
        delete[] data;
        data = new_data;
        cap = new_cap;
    }
    void resize(size_t new_sz, const T& value = T()) {
        if (new_sz > cap) reserve(new_sz * 2);
        for (size_t i = sz; i < new_sz; i++) data[i] = value;
        sz = new_sz;
    }
    T& at(size_t index) { return data[index]; }
    T& operator[](size_t index) { return data[index]; }
    const T& operator[](size_t index) const { return data[index]; }
    T& front() { return data[0]; }
    T& back() { return data[sz - 1]; }
    size_t size() const { return sz; }
    size_t capacity() const { return cap; }
    bool empty() const { return sz == 0; }
    void clear() { sz = 0; }
};
struct string {
    char* data;
    size_t len;
    size_t capacity;
    string() : len(0), capacity(1) {data = new char[capacity];data[0] = '\0';}
    ~string() {delete[] data;}
    string(const char* s) {
        if (!s) {
            len = 0;
            capacity = 1;
            data = new char[capacity];
            data[0] = '\0';
            return;
        }
        len = strlen(s);
        capacity = len + 1;
        data = new char[capacity];
        memcpy(data, s, len + 1);
    }
    string(const string& other) : len(other.len), capacity(other.capacity) {
        data = new char[capacity];
        memcpy(data, other.data, len + 1);
    }
    string(string&& other) noexcept 
        : data(other.data), len(other.len), capacity(other.capacity) {
        other.data = nullptr;
        other.len = 0;
        other.capacity = 1;
        other.data = new char[1];
        other.data[0] = '\0';
    }
    string& operator=(const string& other) {
        if (this != &other) {
            delete[] data;
            len = other.len;
            capacity = other.capacity;
            data = new char[capacity];
            memcpy(data, other.data, len + 1);
        }
        return *this;
    }
    string& operator=(string&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;
            len = other.len;
            capacity = other.capacity;
            other.data = nullptr;
            other.len = other.capacity = 0;
        }
        return *this;
    }
    inline int size() const { return (int)len; }
    inline bool empty() const { return len == 0; }
    inline void clear() { len = 0; data[0] = '\0'; }
    char* begin() { return data; }
    char* end() { return data + len; }
    const char* begin() const { return data; }
    const char* end() const { return data + len; }
    inline const char* c_str() const { return data; }
    inline char& operator[](int i) { return data[i]; }
    inline const char& operator[](int i) const { return data[i]; }
    inline void push_back(char c) {
        if (len + 1 >= capacity) {
            size_t new_capacity = capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        data[len++] = c;
        data[len] = '\0';
    }
    inline int find(const string& sub) const {
        if (sub.len == 0) return 0;
        if (len < sub.len) return -1;
        const char* pos = strstr(data, sub.data);
        if (pos == nullptr) return -1;
        return (int)(pos - data);
    }
    inline int find(const char* sub) const {
        if (!sub || sub[0] == '\0') return 0;
        const char* pos = strstr(data, sub);
        if (pos == nullptr) return -1;
        return (int)(pos - data);
    }
    inline string substr(size_t pos, size_t len = (size_t)-1) const {
        if (pos >= this->len) return string();
        size_t actual_len = this->len - pos;
        if (len < actual_len) actual_len = len;
        string result;
        if (actual_len + 1 > result.capacity) {
            delete[] result.data;
            result.capacity = actual_len + 1;
            result.data = new char[result.capacity];
        }
        memcpy(result.data, data + pos, actual_len);
        result.data[actual_len] = '\0';
        result.len = actual_len;
        return result;
    }
    string& operator+=(const string& other) {
        if (other.len == 0) return *this;
        if (this == &other) {
            string tmp = other;
            return *this += tmp;
        }
        if (len + other.len >= capacity) {
            size_t new_capacity = (len + other.len + 1) * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len + 1);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        memmove(data + len, other.data, other.len + 1);
        len += other.len;
        return *this;
    }
    string& operator+=(const char* s) {
        if (!s || *s == '\0') return *this;
        size_t other_size = strlen(s);
        bool self = (s >= data && s < data + len);
        if (self) {
            string tmp(s);
            return *this += tmp;
        }
        if (len + other_size >= capacity) {
            size_t new_capacity = (len + other_size + 1) * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, data, len + 1);
            delete[] data;
            data = new_data;
            capacity = new_capacity;
        }
        memmove(data + len, s, other_size + 1);
        len += other_size;
        return *this;
    }
    string& operator+=(char c) {
        push_back(c);
        return *this;
    }
    inline void reverse() {
        if (len <= 1) return;
        size_t left = 0,right = len - 1;
        while (left < right) {
            char temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            left++;
            right--;
        }
    }
};
inline string operator+(const string& lhs, const string& rhs) {
    string res = lhs;
    res += rhs;
    return res;
}
inline string operator+(const char* s, const string& str) {
    string res(s);
    res += str;
    return res;
}
inline string operator+(char c, const string& str) {
    string res;
    res.push_back(c);
    res += str;
    return res;
}
inline string operator+(const string& str, const char* s) {
    string res = str;
    res += s;
    return res;
}
inline string operator+(const string& str, char c) {
    string res = str;
    res.push_back(c);
    return res;
}
__attribute__((always_inline))
inline string read_s() {
    string a;
    int c = _gc();
    while (c <= 32) {
        if (c == EOF) return a;
        c = _gc();
    }
    while (c > 32) {
        if (a.len + 1 >= a.capacity) {
            size_t new_capacity = a.capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, a.data, a.len);
            delete[] a.data;
            a.data = new_data;
            a.capacity = new_capacity;
        }
        a.data[a.len++] = c;
        c = _gc();
    }
    a.data[a.len] = '\0';
    return a;
}
__attribute__((always_inline))
inline void getline(string& s) {
    s.clear();
    int c = _gc();
    while (c != '\n' && c != EOF) {
        if (c == '\r') {
            c = _gc();
            if (c == '\n') break;
            continue;
        }
        if (s.len + 1 >= s.capacity) {
            size_t new_capacity = s.capacity * 2;
            char* new_data = new char[new_capacity];
            memcpy(new_data, s.data, s.len);
            delete[] s.data;
            s.data = new_data,s.capacity = new_capacity;
        }
        s.data[s.len++] = c;
        c = _gc();
    }
    s.data[s.len] = '\0';
}
}; // string 类型 字符串 和 vector
using namespace std;
namespace Code{
__attribute__((always_inline))
inline ll read_d() {
    ll x = 0;
    int f = 1,c = _gc();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = _gc();
        if (unlikely(c == EOF)) break;
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = _gc();
    }
    return f == 1 ? x : -x;
}
__attribute__((always_inline))
inline lf read_f() {
    ll ip = 0;
    lf f = 1.00;
    int c = _gc();
    while (c <= 32 && c != EOF) c = _gc();
    if (c == '-') { f = -1.00; c = _gc(); }
    else if (c == '+') { c = _gc(); }
    bool has_digit = false;
    while (c >= '0' && c <= '9') { ip = (ip << 3) + (ip << 1) + (c ^ 48),c = _gc(),has_digit = true; }
    lf fp = 0.00, base = 0.1;
    if (c == '.') {
        c = _gc();
        while (c >= '0' && c <= '9') fp += (c ^ 48) * base,base *= 0.1,c = _gc(),has_digit = true;
    }
    if (!has_digit) return 0.0;
    return (ip + fp) * f;
}
inline void scanf(const char* fmt, ...) {
        va_list args;
        va_start(args, fmt);
        int c;
        while (*fmt) {
            if (*fmt == '%') {
                fmt++;
                if (!*fmt) break;
                if (*fmt == 's') {
                    string* s = va_arg(args, string*);
                    *s = read_s();
                }else if (*fmt == 'd') {
                    int* val = va_arg(args, int*);
                    *val = read_d();
                }else if (*fmt == 'c') {
                    char* val = va_arg(args, char*);
                    *val = _gc();
                }else if (*fmt == 'l') {
                    char c=*(fmt+1);
                    if(c=='f'){
                        fmt++;
                        lf* val = va_arg(args, lf*);
                        *val = read_f();
                    }else if(c=='d'){
                        fmt++;
                        ll* val = va_arg(args, ll*);
                        *val = read_d();
                    }
                }else if (*fmt == 'f') {
                     lf temp = read_f();
                     float* val = va_arg(args, float*);
                     *val = (float)temp;
                }
            } else {
                c = _gc();
                while (c <= 32 && c != EOF && *fmt != '%') c = _gc();
                if (c == EOF) goto end;
            }
            fmt++;
        }
        end:
        va_end(args);
    }
inline void out(const string& a) { const char* p = a.data; for(size_t i=0;i<a.len;++i)_pc(p[i]); }
inline void out(const char* val) { while (*val) _pc(*val++); }
__attribute__((always_inline))
inline void out(ull x) {
    if (x == 0) { _pc('0'); return; }
    char buf[25]; 
    char* ptr = buf + 24;
    *ptr = '\0';
    while (x > 0) { *--ptr = '0' + (char)(x % 10); x /= 10; }
    while (*ptr) _pc(*ptr++);
}
__attribute__((always_inline))
inline void out(ll x) {
    if(x<0){
        _pc('-');
        if(x==LLONG_MIN){
            out("9223372036854775808");
            return;
        }
        out((ull)(-x));
        return;
    }
    out((ull)x);
}
__attribute__((always_inline))
inline void out(int x) { out((ll)x); }
__attribute__((always_inline))
inline void out(unsigned int x) { out((ll)x); }
inline void write_p(lf x, const int& max_decimal) {
    if (x == 0.0) {
        _pc('0');
        if (max_decimal > 0) {
            _pc('.');
            for (int i = 0; i < max_decimal; i++) _pc('0');
        }
        return;
    }
    if (x < 0) { _pc('-'); x = -x; }
    double eps = 0.5;
    for (int i = 0; i < max_decimal; i++) eps *= 0.1;
    x += eps;
    ll int_part = (ll)x;
    out(int_part);
    if (max_decimal <= 0) return;
    _pc('.');
    lf frac_part = x - (lf)int_part;
    for (int i = 0; i < max_decimal; i++) {
        frac_part *= 10.0;
        ll digit = (ll)frac_part;
        _pc('0' + (char)digit);
        frac_part -= (lf)digit;
    }
}
inline void out(const lf& x) { write_p(x, 16); }
inline void out(const float& x) { write_p(x, 8); }
__attribute__((always_inline))
inline void out(const char& val) { _pc(val); }
__attribute__((always_inline))
inline void out(const bool& val) { out(val?"true":"false"); }
void printf(const char* fmt, ...) {
    va_list args;
    va_start(args, fmt);
    while (*fmt) {
        if (*fmt == '%') {
            fmt++; 
            if (!*fmt) break;
            ll precision = -1;
            if (*fmt == '.' && *(fmt+1) == '*') fmt += 2,precision = va_arg(args, int);
            else if (*fmt == '.') {
                fmt++;
                ll p = 0;
                bool has_digit = false;
                while(*fmt >= '0' && *fmt <= '9') {
                    p=(p<<3)+(p<<1)+(*fmt - '0');
                    fmt++;
                    has_digit=true;
                }
                if(has_digit)precision=p;
            }
            switch (*fmt) {
                case 'd':
                case 'i':
                    out(va_arg(args, int));
                    break;
                case 'l':
                    if (*(fmt+1) == 'l' && *(fmt+2) == 'd') out(va_arg(args, ll)),fmt += 2;
                    else if (*(fmt+1) == 'd') out(va_arg(args, ll)),fmt++;
                    else out((ll)va_arg(args, ll));
                    break;
                case 'L':
                     if (*(fmt+1) == 'd') out(va_arg(args, ll)),fmt++;
                     break;
                case 'f':
                case 'F':
                case 'g':
                case 'G':
                    if(precision>=0)write_p(va_arg(args, lf), precision);
                    else out(va_arg(args, lf));
                    break;
                case 's': {
                    const char* s = va_arg(args, const char*);
                    out(s);
                    break;
                }
                case 'c':
                    _pc((char)va_arg(args, int));
                    break;
                case '%':
                    _pc('%');
                    break;
                default:
                    _pc('%');
                    _pc(*fmt);
                    break;
            }
        } else if (*fmt == '\\') {
            fmt++;
            if (!*fmt) break;
            switch (*fmt) {
                case 'n': _pc('\n'); break;
                case 't': _pc('\t'); break;
                case 'r': _pc('\r'); break;
                case '\\': _pc('\\'); break;
                case '"': _pc('"'); break;
                default: 
                    _pc('\\'); 
                    _pc(*fmt); 
                    break;
            }
        } else _pc(*fmt);
        fmt++;
    }
    va_end(args);
}
};
using namespace Code; // C语言输出输入工具
namespace math {
__attribute__((always_inline))
inline lf sqrt(lf x, lf n=2.0) { 
    if(n==2)return __builtin_sqrt(x);
    if(n==3)return __builtin_cbrt(x);
    if(n==4)return sqrt(sqrt(x));
    return pow(x, 1.0L / n); 
}
__attribute__((always_inline))
inline ull gcd(ull a, ull b) {
    if(a==0)return b;
    if(b==0)return a;
    ll shift=ctzll(a|b);
    a>>=ctzll(a),b>>=ctzll(b);
    while(a!=b){
        if(a>b)swap(a, b);
        b-=a,b>>=ctzll(b);
    }
    return a<<shift;
}
inline ull lcm(ull a,ull b){
    if(a==0||b==0)return 0;
    __int128 shift=a/gcd(a, b)*b;
    return (ull)shift;
}
template<typename T>
struct less {bool operator()(const T& a, const T& b) const { return a < b; }};
template<typename T, typename Compare>
__attribute__((always_inline))
void insertion_sort(T a[],int begin,int end,Compare cmp){
    for(int i=begin+1;i<=end;i++){
        T k=move(a[i]);
        int left=begin,right=i-1,pos=i;
        while(left<=right){
            int mid=(right+left)>>1;
            if(cmp(k,a[mid]))right=mid-1,pos=mid;
            else left=mid+1;
        }
        for(int j=i;j>pos;j--)a[j]=move(a[j-1]);
        a[pos]=k;
    }
}
template<typename T>
struct run { int l,r; inline int len()const{return r-l+1;} };
template<typename T, typename C>
__attribute__((always_inline))
inline int find_run(T a[],int n,int st,C cmp){
    if(st>=n-1)return 1;
    bool up=!cmp(a[st+1],a[st]);
    int i=st;
    if(up) while(i<n-1&&!cmp(a[i+1],a[i])) i++;
    else{
        while(i<n-1&&cmp(a[i+1],a[i])) i++;
        int l=st,r=i;
        while(l<r){T t=move(a[l]);a[l]=move(a[r]);a[r]=move(t);l++;r--;}
    }
    return i-st+1;
}
template<typename T, typename C>
__attribute__((always_inline))
inline int get_runs(T a[],int n,run<T>* rs,C cmp){
    int cnt=0,i=0;
    while(i<n){int len=find_run(a,n,i,cmp);rs[cnt].l=i;rs[cnt].r=i+len-1;cnt++;i+=len;}
    return cnt;
}
template<typename T, typename C>
__attribute__((always_inline))
inline void merge_run(T a[],int l1,int r1,int l2,int r2,C cmp){
    int n1=r1-l1+1,n2=r2-l2+1,tot=n1+n2;
    vector<T> tmp(tot,T());
    int i=l1,j=l2,k=0;
    while(i<=r1&&j<=r2){
        if(cmp(a[i],a[j])) tmp[k++]=move(a[i++]);
        else tmp[k++]=move(a[j++]);
    }
    while(i<=r1) tmp[k++]=move(a[i++]);
    while(j<=r2) tmp[k++]=move(a[j++]);
    for(int t=0;t<tot;t++) a[l1+t]=move(tmp[t]);
}
template<typename T>
__attribute__((always_inline))
inline int best_pair(run<T>* rs,int cnt){
    if(cnt<=1)return -1;
    if(cnt==2)return 0;
    int bi=0;lf bp=-1.0;
    for(int i=0;i<cnt-1;i++){
        int l1=rs[i].len(),l2=rs[i+1].len();
        lf rt=(l1<l2)?(lf)l1/l2:(lf)l2/l1;
        lf pw=rt*0.7+(1.0-(lf)i/(cnt-1))*0.3;
        if(pw>bp){bp=pw;bi=i;}
    }
    return bi;
}
template<typename T, typename C>
__attribute__((always_inline))
inline void powersort(T a[],int n,C cmp){
    if(n<=1)return;
    if(n<=16){insertion_sort(a,0,n-1,cmp);return;}
    vector<run<T>> rs(n,T());
    int cnt=get_runs(a,n,rs.data,cmp);
    if(cnt<=1)return;
    if(cnt==2){merge_run(a,rs[0].l,rs[0].r,rs[1].l,rs[1].r,cmp);return;}
    while(cnt>1){
        int id=best_pair(rs.data,cnt);
        if(id<0)break;
        merge_run(a,rs[id].l,rs[id].r,rs[id+1].l,rs[id+1].r,cmp);
        rs[id].r=rs[id+1].r;
        for(int i=id+1;i<cnt-1;i++) rs[i]=rs[i+1];
        cnt--;
    }
}
template<typename T, typename C>
__attribute__((always_inline))
inline bool use_power(T a[],int l,int r,C cmp){
    int n=r-l+1;
    if(n<=64)return 0;
    int sm=min(n/16,128),ok=0;
    for(int i=0;i<sm-1;i++){int p=l+(i*n/sm);if(!cmp(a[p+1],a[p]))ok++;}
    return (lf)ok/sm>0.3;
}
template<typename T,typename C=less<T>>
void mergesort(T a[],int l,int r,C cmp=C()){
    if(l>=r)return;
    int n=r-l+1;
    if(use_power(a,l,r,cmp)){powersort(a+l,n,cmp);return;}
    for(int i=l;i<r+16;i+=16)insertion_sort(a,i,min(i+15,r),cmp);
    vector<pair<int,int>> b;
    for(int i=l;i<=r;i+=16)b.push_back({i,min(i+15,r)});
    T* t=new T[n];
    while(b.size()>1){
        vector<pair<int,int>> nb;
        for(size_t i=0;i<b.size();i+=4){
            size_t st=i,ed=min(i+3,b.size()-1);
            int cnt=ed-st+1;
            int L=b[st].first,R=b[ed].second;
            int idx[4],bs[4],be[4];
            for(int j=0;j<cnt;j++){bs[j]=b[st+j].first;be[j]=b[st+j].second;idx[j]=bs[j];}
            int p=0;
            while(1){
                int mb=-1;
                for(int j=0;j<cnt;j++)
                    if(idx[j]<=be[j]&&(mb==-1||cmp(a[idx[j]],a[idx[mb]]))) mb=j;
                if(mb==-1)break;
                t[p++]=move(a[idx[mb]++]);
            }
            for(int j=0;j<p;j++)a[L+j]=t[j];
            nb.push_back({L,R});
        }
        b=move(nb);
    }
    delete[] t;
}
template<typename T,typename Compare>
void introsort_logic(T a[],int begin,int end,Compare cmp,int d){
    while (end-begin>15){
        int i=begin,cnt=0,is=0;
        while(i<end){
            int run_start=i;
            bool is_ascending=true;
            while(i<end && !cmp(a[i],a[i+1]) && !cmp(a[i+1],a[i]))i++;
            if(i<end)is_ascending=!cmp(a[i+1],a[i]);
            if(is_ascending)while(i<end && !cmp(a[i+1],a[i]))i++;
            else{
                while(i<end && !cmp(a[i],a[i+1]))i++;
                int l=run_start,r=i;is=1;
                while(l<r)swap(a[l],a[r]),l++,r--;
            }
            cnt++,i++;
        }
        if(cnt==1)return;
        if(cnt==2){
            int n=end-begin+1;
            int len1=find_run(a+begin,n,0,cmp);
            int l1=begin,r1=begin+len1-1;
            int l2=r1+1,r2=end;
            merge_run(a,l1,r1,l2,r2,cmp);
            return;
        }
        if(is==1){
            int l=begin,r=end,flag=1;
            while(l<r){
                if(!cmp(a[l],a[l+1]) || !cmp(a[r-1],a[r])){flag=0;break;}
                l++,r--;
            }
            if(flag)return;
        }
        if(d<1){
            mergesort(a,begin,end,cmp);
            return;
        }
        d--;
        int l=begin,h=end,mid=(l+h)>>1;
        if(cmp(a[mid],a[l]))swap(a[l],a[mid]);
        if(cmp(a[h],a[mid]))swap(a[mid], a[h]);
        if(cmp(a[mid],a[l]))swap(a[l],a[mid]);
        T p=a[(l+h)>>1];
        swap(a[mid],a[l]);
        int lt=l,gt=h;
        i=l+1;
        while(i<=gt){
            if(cmp(a[i],p)){
                swap(a[i],a[lt]);
                lt++,i++;
            }else if(cmp(p,a[i])){
                swap(a[i],a[gt]);
                gt--;
            }else i++;
        }
        introsort_logic(a,begin,lt-1,cmp,d);
        begin=gt+1;
        if(begin>=end)return;
    }
    insertion_sort(a,begin,end,cmp);
}
template<typename T,typename Compare=less<T>>
void sort(T a[], int begin, int end, Compare cmp = Compare()) {
    if(begin>=end)return;
    introsort_logic(a,begin,end,cmp,(31-clz(end-begin+1))<<1);
}
};
using namespace math;
struct IO{
    template <typename T>
    IO& operator<<(const T& val){ out(val); return *this; }
    IO& operator>>(int& val) { val=read_d(); return *this; }
    IO& operator>>(ll& val) { val=read_d(); return *this; }
    IO& operator>>(float& val) { val=read_f(); return *this; }
    IO& operator>>(lf& val) { val=read_f(); return *this; }
    IO& operator>>(string& val) { val=read_s(); return *this; }
    IO& operator>>(char& val) { val=_gc(); return *this; }
};
IO cin,cout;
int main(){
    prefetch(_rbuf, 0, 3);
    prefetch(_wbuf, 0, 3);
    _pc('0');
    _return();
}

各位点个赞吧，创作不易啊，再肝我要s了!!!