Weird sorting
You are given N integer numbers a1, a2, ..., aN. 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) |
In this problem you are to figure out whether the given sequence can be sorted or not, applying allowed action zero or more times.
Input
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.
Output
For each test case write "1" if corresponding sequence can be sorted and "0" otherwise. Output must not contain spaces or line breaks.
Example
Input: 5 7 1 3 9 8 2 2 1 0 Output: 10