SPOJ in Armenian

Փոքրիկ Էմիլին իր ծննդյան օրը իր մաթեմատիկայի ուսուցչի կողմից որպես նվեր ստացել էր N+1 երկարության թիվ։ Բայց քանի որ Էմիլին շատ անուշադիր է, նա մեկ օրում կորցրեց իր՝ նվեր ստացած թիվը։ Էմիլին ուսումնասիրել էր իր թվի կամայական 2 հաջորդական թվանշանները և հիշում է N երկարության՝ -1երից, 0ներից և 1երից կազմված հաջորդականություն, որտեղ՝

1. A[i] = -1, երբ iրդ թվանշանը ավելի փոքր է, քան i+1-րդը,
2. A[i] = 0, երբ iրդ թվանշանը հավասար է i+1-րդ թվանշանին,
3. A[i] = 1, երբ iրդ թվանշանը ավելի մեծ է, քան i+1-րդը։

(Այստեղ թվանշանները համարակալված են ձախից աջ՝ 1ից N+1 թվերով, և 1 ≤ i ≤ N)
Հիմա, քանի որ Էմիլին վստահ չէ իր հիշողության վրա, նա ցանկանում է, որ դուք գտնեք հնարավոր ամենամեծ թիվը, որը բավարարում է այս պայմաններին, կամ տեղեկացնել, որ գոյություն չունի այդպիսի թիվ։

Մուտքային տվյալներ

Մուտքում տրված է N ( 1 ≤ N ≤ 10⁶ ) թիվը և N երկարության թվային հաջորդականություն, որի տարրերից յուրաքանչյուրը կա՛մ 1 է, կա՛մ 0, կա՛մ -1։

Ելքային տվյալներ

Ելքում պետք է արտածել ամենամեծ հնարավոր թիվը, կամ -1, եթե այդպիսին չկա։

Օրինակներ