
#ifndef INPUT
#define INPUT
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include <charconv>
typedef long long ll;
typedef long double ld;
#include "constants.h"
#include "random_generators.h"
using namespace std;

int GetNumberFromInput(istream &InputStream, int MinVal, int MaxVal)
{
    string input;
    if (!(InputStream >> input))
    {
        cerr << "no more words in input" << endl;
        assert(true); 
    }

    int Number;
    auto result = std::from_chars(input.data(),
                                  input.data() + input.size(),
                                  Number);

    if (result.ec != errc() || result.ptr != input.data() + input.size()) 
    {
        cerr << "Invalid number " << input << endl;
        assert(true);
    }
    if (Number < MinVal || Number > MaxVal)
    {
        cerr << "Too big / too small " << Number << endl;
        assert(true);
    }
    return Number;
}

class Query
{
public:
    int P, X;
    Query(int _P = -1, int _X = -1)
    {
        P = _P;
        X = _X;
    }
};

class Input
{
public:
    int N, Q;
    vector<int> A;
    int AtSmart(int i, int MinVal = 1, int MaxVal = MAXA)
    {
        if (i < 0)
        {
            return MaxVal;
        }
        if (i >= N)
        {
            return MinVal;
        }
        return A[i];
    }
    vector<Query> Queries;
    Input(int _N = 0, int _Q = 0, int Seed = 0)
    {
        srand(Seed);
        N = _N, Q = _Q;
    }
    void GetFromInput(istream &InputStream)
    {
        N = GetNumberFromInput(InputStream, 2, MAXN);
        Q = GetNumberFromInput(InputStream, 1, MAXQ);
        A.resize(N, 0);
        for (int i = 0; i < N; i++)
        {
            A[i] = GetNumberFromInput(InputStream, 1, MAXA);
        }
        Queries.resize(Q);
        for (int i = 0; i < Q; i++)
        {
            Queries[i].P = GetNumberFromInput(InputStream, 0, N - 1);
            Queries[i].X = GetNumberFromInput(InputStream, 1, MAXA);
        }
    }
    void PrintInput(ostream &OutputStream)
    {
        OutputStream << N << " " << Q << "\n";
        for (int i = 0; i < N; i++)
        {
            OutputStream << A[i] << " \n"[i==N-1];
        }
        for (int i = 0; i < Q; i++)
        {
            OutputStream << Queries[i].P << " " << Queries[i].X << "\n";
        }
    }
    void InitializeARandom(int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        assert(N >= 0 && MinVal >= 1 && MaxVal <= MAXA);
        A.assign(N, 0);
        for (int i = 0; i < N; i++)
        {
            A[i] = RandomWithBias(MinVal, MaxVal, Bias);
        }
    }
    void InitializeWithPeriodicPattern(vector<int> Periodic, int NoiseChance = 0, int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        // Initializes A and Q
        assert(N >= 0 && MinVal >= 1 && MaxVal <= MAXA);
        A.assign(N, 0);
        for (int i = 0; i < N; i++)
        {
            if (RandomInRange(0, 100) < NoiseChance)
            {
                A[i] = RandomWithBias(MinVal, MaxVal, Bias);
            }
            else
            {
                A[i] = Periodic[i % Periodic.size()];
            }
        }
    }
    void InitializeWithNonIncreasingArrayAndQueries(int InterestingQueryChance = 0, int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        // For the subtask with non decreasing array
        A.assign(N, 0);
        for (int i = 0; i < N; i++)
        {
            A[i] = RandomWithBias(MinVal, MaxVal, Bias); 
        }
        sort(A.begin(), A.end(), greater<int>());
        vector<int> original = A;
        set<int> InterestingIndexes;
        for (int i = 0; i < N; i++)
        {
            if (AtSmart(i-1, MinVal, MaxVal) > AtSmart(i+1, MinVal, MaxVal))
            {
                InterestingIndexes.insert(i);
            }
        }
        for (int i = 0; i < Q; i++)
        {
            Query query;
            if (!InterestingIndexes.empty() && RandomInRange(0, 100) < InterestingQueryChance)
            {
                query.P = RandomFromSet(InterestingIndexes);
            }
            else
            {
                query.P = RandomInRange(0, N-1);
            }
            query.X = RandomInRange(AtSmart(query.P + 1, MinVal, MaxVal), AtSmart(query.P - 1, MinVal, MaxVal));
            A[query.P] = query.X;
            assert(AtSmart(query.P - 1, MinVal, MaxVal) >= A[query.P]);
            assert(AtSmart(query.P + 1, MinVal, MaxVal) <= A[query.P]);
            int p = query.P;
            /*if (query.P == 64075)
            {
                cout << " hereee " << A[query.P-1] << " "
                << A[query.P] << " " << A[query.P+1] <<endl; 
            }*/
            if (AtSmart(p-1, MinVal, MaxVal) == AtSmart(p+1, MinVal, MaxVal))
            {
                InterestingIndexes.erase(p);
            }

            if (p-1 >= 0 && AtSmart(p-2, MinVal, MaxVal) > AtSmart(p, MinVal, MaxVal))
            {
                InterestingIndexes.insert(p-1);
            }
            else if (InterestingIndexes.count(p-1))
            {
                InterestingIndexes.erase(p-1);
            }
            
            if (p+1 < N && AtSmart(p, MinVal, MaxVal) > AtSmart(p+2, MinVal, MaxVal))
            {
                InterestingIndexes.insert(p+1);
            }
            else if (InterestingIndexes.count(p+1))
            {
                InterestingIndexes.erase(p+1);
            }
            Queries.push_back(query);
        }
        A = original;
    }
    bool AddQuery(int P, int X)
    {
        if (Queries.size() == Q)
        {
            return false;
        }
        Queries.push_back(Query(P, X));
        return true;
    }
    bool AddRandomQuery(int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        int P = RandomInRange(0, N-1);
        int X = RandomWithBias(MinVal, MaxVal, Bias);
        return AddQuery(P, X);
    }
    bool AddRandomQueryBiasedP(int minP, int maxP, int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        int P = RandomInRange(max(0, minP), min(N-1, maxP));
        int X = RandomWithBias(MinVal, MaxVal, Bias);
        return AddQuery(P, X);
    }
    void RandomRestoringQueries(int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        vector<int> original = A;
        while ((int)Queries.size() < Q)
        {
            AddRandomQuery(MinVal, MaxVal, Bias);
            int ModifiedIndex = Queries.back().P;
            AddQuery(ModifiedIndex, A[ModifiedIndex]);
        }
        A = original;
    }
    void RandomQueries(int MinVal = 1, int MaxVal = MAXA, int Bias = 0)
    {
        //cerr << MinVal << " " << MaxVal << " " << Bias << endl;
        while(Queries.size() < Q)
        {
            AddRandomQuery(MinVal, MaxVal, Bias);
        }
    }
    void AlterSmallBig(int Range = 0, int MinVal = 1, int MaxVal = MAXA)
    {
        A.clear();
        for (int i = 0; i < N; i++)
        {
            if (i & 1)
            {
                A.push_back(RandomInRange(MinVal, MinVal + Range));
            }
            else
            {
                A.push_back(RandomInRange(MaxVal - Range, MaxVal));
            }
        }
        for (int i = 0; i < Q; i++)
        {
            int p = RandomInRange(0, N-1);
            int x = (p & 1) ? RandomInRange(MinVal, MinVal + Range) : RandomInRange(MaxVal - Range, MaxVal);
            AddQuery(p, x);
        }
    }
    void Mountain(int Dir, int MinVal = 1, int MaxVal = MAXA)
    {
        A.clear();
        for (int i = 0; i < N; i++)
        {
            A.push_back(RandomInRange(MinVal, MaxVal));
        }
        if (Dir == 1)
        {
            sort(A.begin(), A.begin() + N/2, less<int>());
            sort(A.begin() + N/2, A.end(), greater<int>());
        }
        else
        {
            sort(A.begin(), A.begin() + N/2, greater<int>());
            sort(A.begin() + N/2, A.end(), less<int>());
        }
        for (int i = 0; i < Q; i++)
        {
            int p = RandomInRange(0, N-1);
            int x = RandomInRange(MinVal, MaxVal);
            AddQuery(p, x);
        }
    }
};

#endif