Happy New Year 2010

You are given N integer numbers a₁, a₂, ..., 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:

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