单调栈,单调队列

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
int res[N];
void solve() {
  a[0] = 1e9 + 1;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] < a[i - 1] && res[i - 1] == -1) {
      res[i] = -1;
    }
    for (int j = i - 1; j >= 0; j--) {
      if (a[j] < a[i]) {
        res[i] = a[j];
        j = -1;
      }
    }
    if (!res[i]) {
      res[i] = -1;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << res[i] << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
int res[N];
stack<int> sta;
void solve() {
  int n;
  cin >> n;
  sta.push(1e9 + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    while (!sta.empty() && sta.top() >= a[i]) sta.pop();
    if (sta.empty()) {
      res[i] = -1;
    } else
      res[i] = sta.top();
    sta.push(a[i]);
  }
  for (int i = 1; i <= n; i++) {
    cout << res[i] << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
int res[N];
int sta[N], top;
void solve() {
  int n;
  cin >> n;
  sta[++top] = 1e9 + 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    while (top && sta[top] >= a[i]) top--;
    if (!top) {
      res[i] = -1;
    } else
      res[i] = sta[top];
    sta[++top] = a[i];
  }
  for (int i = 1; i <= n; i++) {
    cout << res[i] << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N], res_min[N], res_max[N];
void solve() {
  int n, k;
  cin >> n >> k;
  deque<int> deq;  //存储下标
  for (int i = 1; i <= n; i++) cin >> a[i];
  // max
  for (int i = 1; i <= n; i++) {
    //验证队头合理性,大小是否合理
    while (deq.size() && deq.front() <= i - k) deq.pop_front();
    //验证队尾优越性,选大的
    while (deq.size() && a[deq.back()] <= a[i]) deq.pop_back();
    deq.push_back(i);
    if (i >= k) cout << a[deq.front()] << " ";  //一定是头最大
  }
  fuck = deque<int>();  //清空
  cout << endl;
  // min
  for (int i = 1; i <= n; i++) {
    //验证队头合理性,大小是否合理
    while (deq.size() && deq.front() <= i - k) deq.pop_front();
    //验证队尾优越性,选小的
    while (deq.size() && a[deq.back()] >= a[i]) deq.pop_back();
    deq.push_back(i);
    if (i >= k) cout << a[deq.front()] << " ";  //一定是头最小
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N], res_min[N], res_max[N];
int fuck[N], front, back;
void solve() {
  int n, k;
  cin >> n >> k;
  // deque<int> fuck;  //存储下标
  for (int i = 1; i <= n; i++) cin >> a[i];
  // max
  for (int i = 1; i <= n; i++) {
    //验证队头合理性,大小是否合理
    while (back - front + 1 && fuck[front] <= i - k) front++;
    //验证队尾优越性,选大的
    while (back - front + 1 && a[fuck[back]] <= a[i]) back--;
    fuck[++back] = i;
    if (i >= k) cout << a[fuck[front]] << " ";  //一定是头最大
  }
  front = 1;
  back = 0;  //清空
  cout << endl;
  // min
  for (int i = 1; i <= n; i++) {
    //验证队头合理性,大小是否合理
    while (back - front + 1 && fuck[front] <= i - k) front++;
    //验证队尾优越性,选小的
    while (back - front + 1 && a[fuck[back]] >= a[i]) back--;
    fuck[++back] = i;
    if (i >= k) cout << a[fuck[front]] << " ";  //一定是头最小
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 9;
int sta[N], top;
int a[N], l[N], r[N];
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {               //左闭
    while (top && a[sta[top]] >= a[i]) top--;  //找最小
    if (!top)                                  //均比a[i]大
      l[i] = 0;
    else  //存在比a[i]小
      l[i] = sta[top];
    sta[++top] = i;  //压入
  }
  top = 0;                                    //清空
  for (int i = n; i >= 1; i--) {              //右开
    while (top && a[sta[top]] > a[i]) top--;  //找最小
    if (!top)                                 //均比a[i]大
      r[i] = n + 1;
    else  //存在比a[i]小
      r[i] = sta[top];
    sta[++top] = i;  //压入
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    res += a[i] * (r[i] - i) * (i - l[i]);  // a[i]乘两边元素个数的乘积求和
  }
  cout << res;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}