삼각형

수열 $c$가 주어진다. 그리고 다음 형태의 질의를 여러 번 처리해야 한다: 부분 수열 $c_a, c_{a+1}, \dots, c_{b-1}, c_b$ 안에서 세 개의 값을 골라 어떤 삼각형의 세 변의 길이로 삼을 수 있는 경우가 존재하는가?

세 길이 $x \le y \le z$가 삼각형을 이루려면 삼각 부등식 $x + y > z$를 만족해야 한다. $x + y = z$인 경우는 한 직선 위에 놓이므로 삼각형으로 세지 않는다.

첫째 줄에 수열 $c$의 길이인 정수 $n$ ($1 \le n \le 1{,}000{,}000$)이 주어진다. 둘째 줄에는 수열 $c$를 이루는 $n$개의 정수가 주어진다 ($1 \le c_i \le 1{,}000{,}000{,}000$). 셋째 줄에는 질의의 개수인 정수 $p$ ($1 \le p \le 100{,}000$)가 주어진다. 이어지는 $p$개의 줄에는 각각 공백 하나로 구분된 두 정수 $a$와 $b$ ($1 \le a \le b \le 1{,}000{,}000$)가 주어진다.

정확히 $p$개의 줄을 출력한다. 각 질의에 대해 순서대로, 해당 부분 수열 안에서 삼각형의 세 변이 될 수 있는 세 값이 존재하면 TAK을, 존재하지 않으면 NIE를 출력한다. (TAK은 "예", NIE는 "아니오"를 뜻한다.)