Doki Doki Snack Handout

Every exam season the student council hands out snacks to classmates worn out by studying. Seunghwan arrives at the announced place on time, heart pounding at the thought of a snack. Every other student is already there, so Seunghwan gets the last number tag. Worse, a few students cut in line over and over until the order of the queue is a mess. Ingyu, who is handing out the snacks, tells the complaining crowd that he can only hand out snacks in number tag order.

Only then do the students try to line up in order, but the place is so cramped that nobody can move freely. There is one narrow spot to the left of the queue where people can stand single file. Used well, that spot may let everyone get a snack in number tag order.

The snack handout area works like this.

1. The students stand in a single line, and only the person at the head of the queue can move.
2. The line Ingyu set up lets students through in number tag order only, that is $1$ first, then $2$, up to $N$.
3. Between that line and the head of the queue there is a holding spot that people enter single file, one at a time. The person at the head of the queue can step into the holding spot, but nobody in the holding spot can go back to the queue.
4. The holding spot is open on one side only. The person who entered the holding spot last is the first one to leave it for the line.

Given the order of the number tags, decide whether everyone can get a snack in number tag order.

The first line contains $N$, the number of students standing in front of Seunghwan. ($1 \le N \le 1{,}000$)

The second line contains the number tags of those students, listed from the head of the queue to the back. The tags are the integers from $1$ to $N$, each appearing once.

Print Nice if everyone can get a snack in number tag order, and Sad otherwise.