Poruszające się kropki#230
Na osi znajduje się N kropek, i-ta kropka ma współrzędną x_i. Kropka może być przesunięta w dowolnym kierunku. Kropki są tak małe, że jeśli się pokryją, połączą się w jedną kropkę. Kiedy dwie kropki łączą się, kropka o mniejszym indeksie pokrywa kropkę o większym indeksie, zatem numer identyfikator powstałej kropki jest równy mniejszemu z identyfikatorów kropek.
W jednej sekundzie możesz wykonać następującą operację:
Wybierz dowolną kropkę spośród wszystkich obecnie istniejących kropek. Oznaczmy jej indeks jako .
Przesuń kropkę o indeksie z pozycji x_j na pozycję (x_j-1) lub (x_j+1).
Innymi słowy, w jednej sekundzie możesz wybrać kropkę i przesunąć ją w lewo lub w prawo o 1.
Twoim zadaniem jest odpowiedzieć na zapytań. Dla każdego zapytania oblicz najmniejszą liczbę kropek, które mogą pozostać na płaszczyźnie po upływie sekund.
Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą (1 \le n \le 2 \cdot 10^5) — liczbę kropek.
Druga linia wejścia zawiera liczb całkowitych x_i (-10^6 \le x_i \le 10^6) — współrzędne kropek na osi.
Następna linia wejścia zawiera jedną liczbę całkowitą (1 \le q \le 2 \cdot 10^5) — liczbę zapytań.
Następna linia wejścia zawiera liczb całkowitych t_i (0 \le t_i \le 10^{9}).
Wypisz linii — odpowiedzi na odpowiadające zapytania.
Przykład 1
Przykład 2
( punktów): n \le 3;
( punktów): 0 \le x_i \le 20;
( punktów): t_i \le 20;
( punktów): n,q \le 3000;
( punktów): q \le 100;
( punktów): brak dodatkowych ograniczeń.