Subtask 1: ~N, Q \leq 300~.

• Với mỗi truy vấn, duyệt qua tất cả cặp vị trí thỏa mãn và chọn đoạn dài nhất.

Đpt: ~O(N^2 \times Q)~.

Subtask 2: ~N \leq 5000~.

• Vì ~N \leq 5000~ nên ta có thể tìm mọi dãy đồi núi trong ~O(N^2)~. Gọi ~F(l, r)~ là dãy đồi núi dài nhất trong khoảng ~[l, r]~.
• Ta có ~F(l, r) = r - l~, nếu ~[l, r]~ là một dãy đồi núi mà ta đã tính trước,
• Hoặc ~F(l, r) = max(F(l + 1, r), F(l, r - 1))~

Đáp án cho truy vấn ~(l, r)~ là ~F(l, r)~.

Đpt: ~O(N^2 + Q)~.

Subtask 3: ~L_i = 1~.

• Gọi ~l(i)~ là vị trí xa nhất thỏa mãn ~a_i~ là giá trị lớn nhất trong đoạn ~[l(i), i]~. Do các ~L_i = 1~, với mỗi ~i~, ta chỉ cần tìm vị trí ~j~ xa nhất trong đoạn ~[l(i), i]~ thỏa mãn ~a_j = a_i~. Ta gọi hiệu này là ~mx(i)~.
• Đáp án cho truy vấn ~(L_i, R_i)~ là ~max \{mx(i) \}, \ 1 \leq i \leq R_i~.

Đpt: ~O(N + Q)~.

Subtask 4: Các truy vấn không bao nhau

• Nhận xét: Do các truy vấn không bao nhau, ta có thể tách mảng ban đầu thành các khoảng trong truy vấn, và giải độc lập mỗi khoảng theo Subtask 3.

Đpt: ~O(N + Q)~.

Subtask 5: ~a_i \in \{0, 1\}~

Đáp án chỉ xảy ra 2 trường hợp

• Hai đầu mút có giá trị ~1~.
• Các phần tử trong đoạn có giá trị ~0~.

Ta có thể dễ dàng xử lý trường hợp 1, bài toán quy về truy vấn đoạn con dài nhất có ~max = 0~. Đến đây ta có nhiều cách làm, nhưng cách dễ nghĩ nhất vẫn là thực hiện ~merge~ trên ~segment \ tree~. Bài toán xin nhường lại cho bạn đọc.

Đpt: ~O(Q \times log_N)~.

Subtask 6: Không có ràng buộc gì thêm

• Ta sẽ ~sort~ các truy vấn theo ~R_i~ và xử lý offline cho bài toán này.
• Dựa vào ý tưởng của Subtask 3, ta cần ~update~ các ~l(i)~ cho từng truy vấn ~(L, R)~ khác nhau. Tuy nhiên, ta có thể nhận xét rằng những dãy đồi núi không được phép cắt nhau. Ngoài ra, các đầu mút ~a_x, a_y~ cần là ~max~ "cục bộ" trong một khoảng nào đó, tức khi duyệt qua một giá trị ~a_j > a_x~, mọi đoạn ~[x, y]~ với ~y > j~ đều không thỏa mãn. Ta có thể quản lý đồng thời hai tính chất này bằng stack.
• Cụ thể, với mỗi ~a_i~ được thêm vào stack, ta có thể loại bỏ những ~a_j < a_i~ đang có trong stack. Đồng thời, dựa vào tính chất đơn điệu của stack, đối với những ~st.top()~ có giá trị bằng nhau, ta có thể cực đại hóa hiệu ~top_x - top_y~ bằng segment tree.
• Đáp án cho mỗi truy vấn là ~max~ trên khoảng ~L, R~. Tuy nhiên khi xét đến ~i~, đối với những đoạn không nằm trong đoạn ~[l(i), i]~, chúng vẫn chưa được cập nhật lên segment tree, vậy nên ta cần tìm vị trí ~top_x \geq L~ cho mỗi truy vấn và tìm đoạn "đồi núi" xa nhất có một đầu mút là ~top_x~, cuối cùng ta cực đại hóa kết quả cho truy vấn đó.

Ta thu được độ phức tạp ~O((N + Q) \times log_N)~.

Nhận xét: Bài toán không làm việc với nhiều thông tin, nhưng tính chất ~max~ cục bộ của một dãy có thể dễ khiến ta ngộ nhận về thuật toán trong thời gian làm bài. Trên thực tế, thuật toán sử dụng stack tương đối trừu tượng, nên nếu chưa từng gặp dạng bài này, việc nhận ra các tính chất trong thời gian thi dường như rất khó. Chiến thuật tốt nhất cho bài này có lẽ là giải quyết 5 Subtask đầu và chuyển sang bài tiếp theo. Ngoài ra, do tính chất của một dãy khá chặt, ta còn có thể cài những thuật ~O(N \times log^2)~ hay ~O(N \times \sqrt(N)))~ và tối ưu hằng số.

Code tham khảo:

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

const int maxn = 5e5 + 5;
int n, a[maxn], q;
vector<int> grp[maxn];
vector<int> f[maxn];
int le[maxn], last[maxn];
vector<pair<int, int>> que[maxn];
int ans[maxn];

int tree[maxn * 4];
struct segment_tree {
  int n;
  segment_tree() {}
  segment_tree(int n) : n(n) {}
  void update(int ind, int l, int r, int pos, int val) {
    if(l == r) {
      tree[ind] = max(tree[ind], val);
      return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ind << 1, l, mid, pos, val);
    else update(ind << 1 | 1, mid + 1, r, pos, val);
    tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
  }
  int get(int ind, int l, int r, int x, int y) {
    if(l > y || r < x) return 0;
    if(x <= l and r <= y) return tree[ind];
    int mid = (l + r) >> 1;
    return max(get(ind << 1, l, mid, x, y), get(ind << 1 | 1, mid + 1, r, x, y));
  }
  void update(int pos, int val) {
    update(1, 1, n, pos, val);
  }
  int get(int x, int y) {
    return get(1, 1, n, x, y);
  }
} st;
void solve() {
  cin >> n >> q;
  vector<int> vec;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    vec.push_back(a[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for(int i = 1; i <= n; ++i) {
    a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
  }
  st = segment_tree(n);
  for(int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    que[r].push_back(make_pair(l, i));
  }
  vector<int> v;  
  for(int i = 1; i <= n; ++i) {
    while(!v.empty() and a[v.back()] < a[i]) {
      int lst = v.back();
      v.pop_back();
      // xử lý các đoạn nằm trong đoạn [l(i), i]
      while(!v.empty() and a[v.back()] == a[lst]) {
        st.update(v.back(), lst - v.back());
        v.pop_back();
      }
    }
    le[i] = (v.empty() ? 0 : v.back());
    v.push_back(i);
    if(a[le[i]] == a[i]) {
      last[i] = last[le[i]];

      st.update(last[i], i - last[i]);
    }
    else {
      last[i] = i;
    }
    grp[a[i]].push_back(i);

//    cout << i << " " << last[i] << endl;
//    for(int i = 1; i <= n; ++i) {
//      cout << st.get(i, i) << ' ';
//    }
//    cout << endl;

    for(auto e:que[i]) {
      int l = e.first, id = e.second;
      ans[id] = st.get(l, i);      
      int pos = lower_bound(v.begin(), v.end(), l) - v.begin();
      // xử lý đoạn không bao nhau
      ans[id] = max(ans[id], grp[a[v[pos]]].back() - v[pos]);
    }
  }
  for(int i = 1; i <= q; ++i) {
    cout << ans[i] << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();
  return 0;
}