URI Online Judge | 1877

# Sansa's Snow Castle

By Ricardo Oliveira, UFPR Brazil

Timelimit: 1

Robin: "What are you doing?"
Sansa: "I'm building my home, Winterfell."

Sansa is building a snow castle at the garden of The Eyrie. The snow castle is meant to resemble the actual castle of Winterfell.

The snow castle can be described as a sequence of N snow towers, numbered from 1 to N from the left to the right. The height of tower i (1 ≤ i ≤ N) is equal to hi centimeters.

Sansa says the castle is beautiful if it consists on a sequence of K "peaks" alternated with K-1 "valleys", like the actual castle of Winterfell. In other words, the castle is beautiful if there is a sequence of K towers T1 < T2 < ... < TK such that:

• The heights of the towers in the interval [1,T1] are in ascending order;
• There is a "valley" in the interval [Ti,Ti+1], for all 1 ≤ i < K;
• The heights of the towers in the interval [TK,N] are in descending order.

There is a "valley" in an interval [A, B] if B ≥ A+2 and there is some tower J, A ≤ J ≤ B, such that the heights of the towers in the interval [A,J] are in descending order, and the heights of the towers in the interval [J,B] are in ascending order.

Help Sansa to determine whether her castle is beautiful or not!

## Input

The first line contains two integers N  and K (1 ≤ N ≤ 1000, 1 ≤ K ≤ N). The second line contains N integers h1, h2, ..., hN (1 ≤ hi ≤ 100), the heights of the towers, in centimetres. The first and the last tower will always be 1 centimeter high. No two consecutive towers will have the same height.

## Output

Print a line containing the word beautiful if the given castle is beautiful, or the word ugly otherwise.

 Input Samples Output Samples 9 3 1 2 3 2 4 3 1 2 1 beautiful
 5 3 1 2 1 2 1 ugly