#include <cstdio> #include <tuple> #include <algorithm> const int N = 100000 + 10; int n, a[N]; std::pair<int, int> f[20][N]; int init() { int q; scanf("%d%*d%d", &n, &q); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); static int stk[N]; f[0][n].second = n; for (int i = 1, top = 0; i <= n; ++i) { for (; top && a[i] >= a[stk[top]]; --top) f[0][stk[top]].second = i; stk[++top] = i; } f[0][1].first = 1; for (int i = n, top = 0; i > 0; --i) { for (; top && a[i] >= a[stk[top]]; --top) f[0][stk[top]].first = i; stk[++top] = i; } for (int i = 1; i < 20; ++i) { for (int j = 1; j <= n; ++j) { int x, y; std::tie(x, y) = f[i - 1][j]; f[i][j] = {std::min(f[i - 1][x].first, f[i - 1][y].first), std::max(f[i - 1][x].second, f[i - 1][y].second)}; } } return q; } int main() { for (int q = init(); q--;) { int l, r; scanf("%d%d", &l, &r); if (l > r) std::swap(l, r); int ans = 0, x = l, y = l; for (int i = 19; i >= 0; --i) { if (std::max(f[i][x].second, f[i][y].second) >= r) continue; ans += 1 << i; std::tie(x, y) = std::make_tuple(std::min(f[i][x].first, f[i][y].first), std::max(f[i][x].second, f[i][y].second)); } l = y; x = y = r; for (int i = 19; i >= 0; --i) { if (std::min(f[i][x].first, f[i][y].first) <= l) continue; ans += 1 << i; std::tie(x, y) = std::make_tuple(std::min(f[i][x].first, f[i][y].first), std::max(f[i][x].second, f[i][y].second)); } printf("%d\n", ans); } return 0; }

railway_trip.cpp: In function 'int init()':
railway_trip.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%*d%d", &n, &q);
                           ^
railway_trip.cpp:14:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                  ^
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:39:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &l, &r);
                          ^