-- 暴力 -- 删除多余元素 -- 单调性 -- 极值
1.保证滑动窗口的合法性
2.保证滑动窗口的性质（单调性）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int num[N],q[N],head,tail = -1;

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>num[i];
        if(i - k + 1 > q[head])
            head++;
        while(head <= tail and num[i] <= num[q[tail]])
            tail--;
        q[++tail] = i;
        if(i - k + 1 >= 0) cout<<num[q[head]]<<" ";
    }
    cout<<endl;

    head = 0,tail = -1;
    for(int i=0;i<n;i++){
        cin>>num[i];
        if(i - k + 1 > q[head])
            head++;
        while(head <= tail and num[i] >= num[q[tail]])
            tail--;
        q[++tail] = i;
        if(i - k + 1 >= 0) cout<<num[q[head]]<<" ";
    }
    return 0;
}

暴力
    2层循环
单调栈
    有些元素永远不可能作为答案输出，删除这些元素可以提高效率
    在a[x] ≥ a[y]且x < y的情况下,前者肯定不会是答案

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int stk[N],top;

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(top and stk[top] >= x) top--;
        if(top)
            cout<<stk[top]<<" ";
        else
            cout<<-1<<" ";
        stk[++top] = x;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
// tail初始化为-1的好处是可以和head从同一个下标开始计算
int q[N],head,tail = -1;

void push(int x){
    q[++tail] = x;
}

void pop(){
    head++;
}

bool empty(){
    if(head <= tail)
        return false;
    return true;
}

int query(){
    return q[head];
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        string s;
        cin>>s;
        if(s == "push"){
            cin>>x;
            push(x);
        }
        else if(s == "pop"){
            pop();
        }
        else if(s == "empty"){
            if(empty())
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else if(s == "query"){
            cout<<query()<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int stk[N],top;

// 指针从0开始,下标值即数量
void push(int x){
    stk[++top] = x;
}

void pop(){
    top--;
}

bool empty(){
    if(top > 0)
        return false;
    return true;
}

int query(){
    return stk[top];
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        string s;
        cin>>s;
        if(s == "push"){
            cin>>x;
            push(x);
        }
        else if(s == "pop"){
            pop();
        }
        else if(s == "empty"){
            if(empty())
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else if(s == "query"){
            cout<<query()<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int e[N],l[N],r[N],idx;

void init(){
    l[1] = 0;
    r[0] = 1;
    idx = 2;
}

// 在第k个点的右边添加一个点
void add(int k,int x){
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

// 删除第k个点
void remove(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main(){
    init();
    int n;
    cin>>n;
    while(n--){
        int k,x;
        string op;
        cin>>op;
        if(op == "L"){
            cin>>x;
            add(0,x);
        }
        else if(op == "R"){
            cin>>x;
            add(l[1],x);
        }
        else if(op == "D"){
            cin>>k;
            // idx从2开始,k从1开始,所以k需要加1
            remove(k + 1);
        }
        else if(op == "IL"){
            cin>>k>>x;
            // 在k左边插入就是在l[k]的右边插入
            add(l[k + 1],x);
        }
        else if(op == "IR"){
            cin>>k>>x;
            add(k + 1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]){
        cout<<e[i]<<" ";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int head,e[N],ne[N],idx;

void init(){
    head = -1;
    idx = 1; //下标从1开始
}

//重点是需要记住单链表的操作过程
void addToHead(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    int n;
    cin>>n;
    init();
    while(n--){
        char op;
        int k,x;
        cin>>op;
        if(op == 'H'){
            cin>>x;
            addToHead(x);
        }
        else if(op == 'D'){
            cin>>k;
            if(k == 0)
                head = ne[head];
            else
                remove(k);
        }
        else{
            cin>>k>>x;
            add(k,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]){
        cout<<e[i]<<" ";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N=110;
const double eps=1e-9;
int n;
double a[N][N];

int gauss()
{
    int c,r;
    for(c=0,r=0;c<n;c++)
    {
        int maxr=r;
        for(int i=r;i<n;i++)
            if(fabs(a[maxr][c])<fabs(a[i][r]))
                maxr=i;
        if(fabs(a[maxr][c])<eps)
            continue;
        for(int j=c;j<n+1;j++)
            swap(a[maxr][j],a[r][j]);
        for(int j=n;j>=c;j--)
            a[r][j]/=a[r][c];
        for(int i=r+1;i<n;i++)
            for(int j=n;j>=c;j--)
                a[i][j]-=a[i][c]*a[r][j];
        r++;
    }
    if(r<n)
    {
        for(int i=r;i<n;i++)
            if(fabs(a[i][n])>eps)
                return 0;
        return 2;
    }
    for(int i=n-2;i>=0;i--)
        for(int j=i+1;j<n;j++)
            a[i][n]-=a[i][j]*a[j][n];
    return 1;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin>>a[i][j];
    int ans=gauss();
    if(ans==0)
        cout<<"No solution";
    else if(ans==1)
    {
        for(int i=0;i<n;i++)
        {
            if(fabs(a[i][n])<eps)
                a[i][n]=0;
            printf("%.2f\n",a[i][n]);
        }
    }
    else
        cout<<"Infinite group solutions";
}

#include<bits/stdc++.h>
using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,m,x,y;
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if(b%d==0)  cout<<(long long)x*(b/d)%m<<endl;
        else cout<<"impossible"<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;

int quickPower(int a,int k,int p)
{
    long long res=1;
    while(k)
    {
        if(k&1)
            res=res*a%p;
        k>>=1;
        a=(long long)a*a%p;
    }
    return res;
}

int main()
{
    int n,a,p;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>p;
        if(a%p) cout<<quickPower(a,p-2,p)<<endl;
        else cout<<"impossible"<<endl;
    }
}