Description

萌新 和大佬 在玩吃糖游戏，规则如下：

一共有n 堆糖排成一排，每堆糖的个数为ai​。两个人轮流吃糖，大佬先手。每次吃糖只能取最左一堆或最右一堆，且必须取完。最后吃得糖多者获胜。假设双方都足够聪明，最后谁能够获胜呢？

Format

Input

第一行是一个正偶数n，表示糖的堆数。

第二行是n个正整数，a[1],a[2]……a[n]，表示每堆糖的个数。

Output

输出一个字符串“dalao”或“mengxin”，表示胜者的名字。

Samples

4
2 3 3 3

dalao

Hint

1<n<100000;

1<A[i]<100000

所有a[i]和为奇数