Jaś uwielbia rozwiązywać problemy obliczeniowe przeznaczone dla komputerów. Namówił swoją mamę na następującą zabawę: mama poda ciąg n liczb naturalnych (niekoniecznie różnych), a następnie q zapytań o jego podciągi. Dla każdego zapytania Jaś musi szybko odpowiedzieć, czy istnieje taka trójka x, y, z wyrazów na różnych pozycjach w danym podciągu, że da się skonstruować trójkąt o długościach boków x, y, z i niezerowym polu powierzchni. Napisz program, który pomoże mamie Jasia szybko weryfikować jego odpowiedzi.
Pierwszy wiersz zawiera dwie liczby naturalne n i q (1 <= n <= 500000, 1 <= q <= 500000) oznaczające odpowiednio: długość ciągu podanego przez mamę i liczbę zapytań. Drugi wiersz zawiera ciąg n liczb naturalnych ti oddzielonych spacją (1 <= ti <= 1018). Kolejne q wierszy zawiera po jednym zapytaniu, każde w postaci pary liczb naturalnych aj, bj oddzielonych spacją (1 <= aj <= bj <= n), oznaczające podciąg taj, taj+1, ..., tbj-1, tbj.
Wyjście powinno zawierać q wierszy, w wierszu o numerze i powinno znajdować się słowo TAK, jeżeli dla i-tego podciągu istnieje taka trójka jego wyrazów na różnych pozycjach, że spełnione są warunki zadania lub słowo NIE w przeciwnym przypadku.
[Zgłoś rozwiązanie] [Moje zgłoszenia]