import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.List; import java.util.TreeSet; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); int[] x = new int[n]; for (int i = 0; i < n; i++) { x[i] = Integer.parseInt(sa[i]); } int rn = (int) Math.sqrt(n) + 1; List> list = new ArrayList<>(rn); for (int i = 0; i < rn; i++) { int start = rn * i; int end = Math.min(n, start + rn); TreeSet set = new TreeSet<>(); set.add(-1000000000); set.add(2000000000); for (int j = start; j < end; j++) { set.add(x[i]); } list.add(set); } int q = Integer.parseInt(br.readLine()); PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); int l = Integer.parseInt(sa[0]) - 1; int r = Integer.parseInt(sa[1]); int y = Integer.parseInt(sa[2]); int ll = (l - 1) / rn + 1; int rr = r / rn; int ans = Integer.MAX_VALUE; int end = Math.min(ll * rn, r); for (int j = l; j < end; j++) { ans = Math.min(ans, Math.abs(x[j] - y)); } for (int j = ll; j < rr; j++) { TreeSet set = list.get(j); int ol = set.floor(y); ans = Math.min(ans, y - ol); int or = set.ceiling(y); ans = Math.min(ans, or - y); } for (int j = Math.max(rr * rn, l); j < r; j++) { ans = Math.min(ans, Math.abs(x[j] - y)); } pw.println(ans); } pw.flush(); br.close(); } }