## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 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

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````
n, k = [int(x) for x in input().split()]
e = [int(x) for x in input().split()]
p = v = 0

a = ''
for c, i in enumerate(e[1:]):
if i > e[c]:
if a == 'd': v += 1
a = 's'
elif i < e[c]:
if a == 's': p += 1
a = 'd'

print('beautiful') if k == p == v+1 else print('ugly')
``````
Copy The Code &

Input

cmd
9 3
1 2 3 2 4 3 1 2 1

Output

cmd
beautiful