KPSORT - 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

Added by:Pavel Kuznetsov
Date:2008-04-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IT Festival Arkhangelsk 2007

hide comments
2016-06-06 16:51:49 Piyush Kumar
Solved it after many wrong answers. Can't prove my solution :(
2012-06-25 14:02:07 StupidGuy
Could someone post more test Cases?
2012-05-22 20:50:30 Adrian Jaskó³ka
Why solution for this problem works?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.