#include #include // #include // using namespace atcoder; // using mint = modint998244353; using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (n); ++i) #define test puts("Test"); #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #pragma GCC target("popcnt") // 下、右、上、左 int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; using u64 = uint64_t; struct BitVector { int n; // bit列 vector A; // bit列popcntの累積和 vector rank64; BitVector() {} BitVector(int N) { n = (N+63) / 64; A.resize(n+1); rank64.resize(n+1); } int popcnt(u64 x) {return __builtin_popcountll(x);} void set(int i) { A[i/64] |= 1ull << (i & 63); } // i/64のbit列のi%64部分に+1 void build() { for (int i=0; i dat; WaveletMatrix(vector A) : N(A.size()) { int mx = A.empty() ? 0 : *max_element(A.begin(), A.end()); H = max(1, (int)bit_width((unsigned)mx)); dat.resize(H); vector nxt(N); for (int h=H-1; h >= 0; --h) { BitVector bv(N); for (int i=0; i> h) & 1) bv.set(i); bv.build(); dat[h] = std::move(bv); int p0 = 0, p1 = N - dat[h].rank(N); for (int i=0; i < N; i++) { if (A[i] >> h & 1) nxt[p1++] = A[i]; else nxt[p0++] = A[i]; } swap(A,nxt); } } tuple get_subtree_range(int h, int l, int r) { int a0 = l - dat[h].rank(l), a1 = dat[h].rank(l); int b0 = r - dat[h].rank(r), b1 = dat[h].rank(r); int c0 = N - dat[h].rank(N); return make_tuple(a0, b0, c0 + a1, c0 + b1); } int kth_smallest(int l, int r, int k) { assert(0 <= l && l <= r && r <= N && 0 <= k && k < r - l); return kth_smallest_rec(H, l, r, k); } int kth_largest(int l, int r, int k) { assert(0 <= l && l <= r && r <= N && 0 <= k && k < r - l); return kth_smallest_rec(H, l, r, r-l-1-k); } int count_less(int l, int r, int x) { assert(0 <= l && l <= r && r <= N); if (x >= (1LL << H)) return r - l; if (x <= 0) return 0; return count_rec(H, l, r, x); } optional prev_value(int l, int r, int upper) { int c = count_less(l, r, upper); if (c == 0) return nullopt; return kth_smallest(l, r, c-1); } optional next_value(int l, int r, int lower) { int c = count_less(l, r, lower); if (c == r - l) return nullopt; return kth_smallest(l,r,c); } int range_freq(int l, int r, int lower, int upper) { assert(0 <= l && l <= r && r <= N); return count_less(l,r,upper) - count_less(l,r,lower); } int kth_smallest_rec(int h, int l, int r, int k) { if (h == 0) return 0; auto [l0, r0, l1, r1] = get_subtree_range(h - 1, l, r); int left_size = r0 - l0; if (k < left_size) { return kth_smallest_rec(h-1, l0, r0, k); } else { return (1 << (h-1)) + kth_smallest_rec(h-1, l1, r1, k - left_size); } } int count_rec(int h, int l, int r, int k) { if (h == 0) return 0; auto [l0, r0, l1, r1] = get_subtree_range(h-1, l, r); int left_size = r0-l0; int i = k >> (h-1); if (i&1) { return left_size + count_rec(h-1, l1, r1, k); } else { return count_rec(h-1, l0, r0, k); } } }; int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; cin >> N; vector X(N); rep(i,N) cin >> X[i]; WaveletMatrix WM(X); int Q; cin >> Q; while (Q--) { int l,r,x; cin >> l >> r >> x; int ans = INT_MAX; if (auto p = WM.prev_value(l-1,r,x)) ans = min(ans, x - *p); if (auto q = WM.next_value(l-1,r,x)) ans = min(ans, *q - x); cout << ans << "\n"; } return 0; }