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