The Fat Rat and his friend Cerealguy have had a bet whether at least a few oats are going to descend to them by some clever construction. The figure below shows the clever construction.

A more formal description of the clever construction is as follows. The clever construction consists of n rows with scales. The first row has n scales, the second row has (n-1) scales, the i-th row has (n-i+1) scales, the last row has exactly one scale. Let's number the scales in each row from the left to the right, starting from 1. Then the value of w_i,k in kilograms (1≤i≤n;1≤k≤n-i+1) is the weight capacity parameter of the k-th scale in the i-th row.

If a body whose mass is not less than w_i,k falls on the scale with weight capacity w_i,k, then the scale breaks. At that anything that the scale has on it, either falls one level down to the left (if possible) or one level down to the right (if possible). In other words, if the scale w_i,k (i<n) breaks, then there are at most two possible variants in which the contents of the scale's pan can fall out: all contents of scale w_i,k falls either on scale w_i+1,k-1 (if it exists), or on scale w_i+1,k (if it exists). If scale w_n,1 breaks, then all its contents falls right in the Fat Rat's claws. Please note that the scales that are the first and the last in a row, have only one variant of dropping the contents.

Initially, oats are simultaneously put on all scales of the first level. The i-th scale has a_i kilograms of oats put on it. After that the scales start breaking and the oats start falling down in some way. You can consider everything to happen instantly. That is, the scale breaks instantly and the oats also fall instantly.

The Fat Rat is sure that whatever happens, he will not get the oats from the first level. Cerealguy is sure that there is such a scenario, when the rat gets at least some number of the oats. Help the Fat Rat and the Cerealguy. Determine, which one is right.