Submit | All submissions | Best solutions | Back to list |
SNYC2 - 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: | kuszi |
Date: | 2009-12-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE |
Resource: | IT Festival Arkhangelsk 2007 (KPSORT problem posted by Pavel Kuznetsov) |