#include template struct sparse_table { using size_t = std::size_t; template using vector = std::vector; size_t sz; vector> min; vector log2; sparse_table() {} template sparse_table(iterator first, iterator last) : sz(distance(first, last)), min(1, vector(sz)) { initialize(first); } template void initialize(iterator dat) { log2.resize(sz + 2); log2[1] = 0; for (size_t i = 2; i < sz + 2; ++i) { log2[i] = log2[i / 2] + 1; } if (sz) min.reserve(log2[(sz + 1) / 2] + 2); std::iota(min[0].begin(), min[0].end(), 0); for (size_t i = 1; i < 30; ++i) { size_t w = 1 << i; if (sz + 1 < w) break; vector next(sz + 1 - w); for (size_t l = 0; l < sz + 1 - w; ++l) { size_t left = min[i - 1][l], right = min[i - 1][l + w / 2]; next[l] = dat[left] < dat[right] ? left : right; } min.emplace_back(move(next)); } } template size_t rmq(Container const &x, size_t l, size_t r) const { size_t i = log2[r - l]; size_t rr = r - (1 << i); l = min[i][l], r = min[i][rr]; return x[l] < x[r] ? l : r; } }; using namespace std; using ll = long long; #define int ll vector solve(const vector &a, const vector> &qs) { int n = a.size(); vector ds; for (int i = 1; i < n; ++i) { ds.push_back(a[i] - a[i - 1]); } const auto st = sparse_table(ds.begin(), ds.end()); vector ans; for (auto q : qs) { int l, r; tie(l, r) = q; int idx = st.rmq(ds, l, r); ans.push_back(ds[idx] >= 0 ? 1 : 0); } return ans; } signed main() { int n; cin >> n; vector a(n); // forall non-negative? non-positive? for (int i = 0; i < n; ++i) { cin >> a[i]; } int q; cin >> q; vector> qs(q); for (auto &q : qs) { int l, r; cin >> l >> r; q = make_pair(l, r); } vector xs = solve(a, qs); for (auto &x : a) x = -x; vector ys = solve(a, qs); for (int i = 0; i < q; ++i) { cout << xs[i] << ' ' << ys[i] << '\n'; } }