SP2649 KPSORT - Weird sorting

You are given **N** integer numbers a $ _{1} $ , a $ _{2} $ , ..., a $ _{N} $ . All you need to do is to sort them in non-decreasing order. The bad thing is you are only allowed to perform one action. You can pick any number in the sequence and then reverse all elements to the left and to the right of it. For example, suppose you were given the sequence (7, 1, 3, 9, 8) then, depending on the picked number you'll get the following results: Picked number Resulting sequence 7(7, 8, 9, 3, 1)1(7, 1, 8, 9, 3)3(1, 7, 3, 8, 9)9(3, 1, 7, 9, 8)8(9, 3, 1, 7, 8)

Input will contain multiple test cases (not more than 100). Each case will start with the number of elements in the sequence N (1 ≤ N ≤ 100), followed by the N integers not exceeding 1000 by the absolute value. Input ends with the value N = 0.

For each test case write "1" if corresponding sequence can be sorted and "0" otherwise. Output must not contain spaces or line breaks.