Problem I
Hextech Ordnance
Heimerdinger is visiting the prestigious Simons Institute, the world’s leading research institute on the theory of computing — and more recently, hextech. He is helping the researchers examine the strange properties of hextech ordnance. A sample of hextech ordnance gives $n$ readings, $a_1, a_2, \ldots , a_n$. Heimerdinger realizes that this ordnance is stable if and only if for all $1 \leq k \leq n$, there exists at least $k$ subarrays such that the difference between the the maximum and minimum elements of the subarray is at most $k$, and the length of the subarray is at least 2. Formally, the ordnance is stable if for all $1 \leq k \leq n$, there exists at least $k$ subarrays $[i, j]$ such that:
-
$1 \leq i < j \leq n$,
-
$\max (a_i, a_{i+1}, \ldots , a_j) - \min (a_i, a_{i+1}, \ldots , a_j) \leq k$.
Heimerdinger doesn’t quite know how to check the readings himself, and has already assigned all of his students the essential task of researching mustache volumizers. As such, he asks you—a young rising researcher at Simons Institute—for your help.
Input
The first line of input contains a single integer $n$ ($1 \leq n \leq 10^6$), the number of readings. The second line contains $n$ space-seperated integers $a_1, a_2, \ldots , a_n$ ($0 \leq a_i \leq 10^9$), the readings from the hexcore.
Output
Output stable if the ordnance is stable. Otherwise, output unstable.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 10 3 8 2 6 5 3 4 4 10 |
stable |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 3 15 19 7 15 18 17 4 19 1 |
unstable |
