Masz dany ciąg liczbowy c i ciąg zapytań postaci: "Czy w ciągu c_a, c_a+1, ..., c_b-1, c_b istnieje trójka liczb taka, że istnieje trójkąt, którego długościami boków są te liczby?".

입력 형식

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 1 000 000) będąca długością ciągu c. W drugim wierszu znajduje się n liczb całkowitych oznaczających ciąg c (1 ≤ c_i ≤ 1 000 000 000). W trzecim wierszu znajduje się jedna liczba całkowita p (1 ≤ p ≤ 100 000). Każdy z następnych p wierszy zawiera dwie liczby całkowite a i b (1 ≤ a ≤ b ≤ 1 000 000) oddzielone pojedynczym odstępem.

출력 형식

Na standardowe wyjście należy wypisać dokładnie p wierszy zawierających jedno słowo TAK lub NIE, w zależności od tego, czy w danym podciągu istnieje trójka liczb taka, że istnieje trójkąt, którego długościami boków są te liczby.

예제 입력

4
1 2 3 4
3
1 1
1 2
1 4

예제 출력

NIE
NIE
TAK