Informática Iniciante – Semana 71

O Castelo de Neve de Sansa

Robin: “O que você está fazendo?”
Sansa: “Estou construindo minha casa, Winterfell.”

Sansa está construindo um castelo de neve no jardim do Ninho da Águia. O castelo de neve é feito para parecer com o verdadeiro castelo de Winterfell.

O castelo de neve pode ser descrito como uma sequência de $$N$$ torres de neve, numeradas de $$1$$ a $$N$$ da esquerda para a direita. A altura da torre $$i$$ $$(1 \leq i \leq N)$$ é igual a $$h_i$$ centímetros.

Sansa diz que o castelo é bonito se ele consiste em uma sequência de $$K$$ “picos” alterados com $$K-1$$ “vales”, como o castelo de Winterfell. Em outras palavras, o castelo é bonito se existe uma sequência de $$K$$ torres $$T_1, T_2, T_3, …, T_K$$ tal que:

• As alturas das torres no intervalo $$[1, T_1]$$ estão em ordem crescente.
• Existe um “vale” no intervalo $$[T_i, T_{i+1}]$$, para todo $$1 \leq i \leq K$$.
• As alturas das torres no intervalo $$[T_K, N]$$ estão em ordem decrescente.

Existe um “vale” em um intervalo $$[A, B]$$ se $$A + 2 \leq B$$ e existe alguma torre $$J$$, $$A \leq J \leq B$$, tal que as alturas das torres no intervalo $$[A, J]$$ estão em ordem decrescente, e as alturas das torres no intervalo $$[J, B]$$ estão em ordem crescente.

Ajude Sansa a determinar se seu castelo é bonito ou não!

Entrada

A primeira linha contém dois inteiros $$N$$ e $$K$$ $$(1 \leq N \leq 1000, 1 \leq K \leq N)$$. A segunda linha contém $$N$$ inteiros $$h_1, h_2, …, h_N$$ $$(1 \leq h_i \leq 100)$$, as alturas das torres, em centímetros. A primeira e a última torre sempre terão 1 centímetro de altura. Duas torres consecutivas nunca terão a mesma altura.

Saída