Schody do nieba, autostrada do piekła

To czy trafisz do nieba, czy do piekła, zależy od twoich dobrych uczynków, które stworzą ci odpowiednie schody. Każdy dobry uczynek, to kolejny stopień takich schodów. Natomiast złe uczynki tworzą schody do piekła. Każdy kolejny zły uczynek przybliża cię do wiecznego potępienia. Na twoje szczęście (lub nie) musisz wymazać z pamięci jeden uczynek. Dopiero po tym fakcie będzie zdecydowane, gdzie trafisz: do nieba, jeśli maksymalna liczba dobrych uczynków z rzędu będzie nie mniejsza niż maksymalna liczba złych uczynków.

Schody do nieba, to spójny podciąg reprezentujący wysokości stopni schodów. Taki ciąg musi być niemalejący i musi składać się z co najmniej dwóch różnych liczb. Liczba schodów, to liczba różnych liczb w tym podciągu.

Schody do piekła, to spójny podciąg reprezentujący wysokość  stopni schodów. Taki podciąg musi być nierosnący i składać się z co najmniej dwóch różnych liczb. Liczba schodów, to liczba różnych liczb w podciągu.

W danym ciągu znajdują się schody do nieba, jeśli maksymalna długość schodów do nieba jest nie mniejsza niż długość schodów do piekła (po usunięciu jednego wyrazu w ciągu).

Napisz program, który określi, czy zasłużyłeś na niebo, czy piekło, jeśli wiesz, że musisz z ciągu usunąć jedną liczbę i zależy ci, aby trafić do nieba.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę zestawów danych (n < 1001).

Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu jedna liczba t określająca długość ciągu (t < 10001), następnie w drugim wierszu t liczb naturalnych dodatnich, gdzie żadna jest nie większa niż milion. Gwarantuje się, że każdy ciąg zawiera co najmniej trzy różne liczby.

Wyjście

Dla każdego zestawu danych napis niebo, jeśli trafisz do nieba, w przeciwnym razie pieklo.

Przykład

Wejście:
2
12
1 2 3 2 3 5 7 6 5 3 4 6
10
9 8 7 6 5 4 3 2 3 2

Wyjście:
niebo
pieklo

Szkic rozwiązania

Rozwiązanie liniowe. W tym zadaniu należy rozpatrzeć kilka sytuacji. Najważniejsze z nich przedstawię na przykładach.

1. 1 2 3 4 6 5 4 3 2 1 – przypadek, gdy ciąg malejący jest o 1 dłuższy od rosnącego i długość ta wystąpiła tylko raz. Po usunięciu dowolnego wyrazu z tego ciągu idziemy do nieba.
2. 1 2 3 4 6 5 4 3 2 1 6 5 4 3 2 1 – w tym przypadku idziemy do piekła, ponieważ usunięcie jednego wyrazu z ciągu malejącego nic nie zmieni
3. 1 2 3 6 5 6 5 4 3 2 – usunięcie pierwszej szóstki sprawi, że pójdziemy do nieba
4. 1 2 7 10 8 9 8 7 6 5 – usunięcie liczby dziesięć sprawi, że pójdziemy do nieba

Dodatkowo dołączam test, który zatrzymał chociaż na chwilę każdego.