Vova was walking along one of Shenzhen streets when he noticed young pear
trees, growing along the pavement. Each tree had a plaque attached to it
containing some number. Vova walked around all n trees and found out
that the numbers on the plaques are pairwise distinct and fit the limits
from 1 to n. Obviously, the trees were first planned to be planted in
the given order, but at the moment they were strangely mixed: the sixth
one, then the fourth one, then the third one, then the fifth one...
There was an ice cream tray nearby. The ice cream seller noticed Vova
staring at the pear trees with a bewildered look and told him that he saw
the trees planted. The foreman entrusted two workers with the task and
told them to plant the trees according to the numbers on the plaques. Then
he left and the workers divided the trees between themselves and started
working. As the foreman wasn't specific about the increasing or decreasing
order of numbers on the plaques, each worker made his own decision without
consulting the partner. Both workers planted trees moving in the same
direction, from the same end of the street.
Let's look at the sample. Let's assume that n = 8 and the workers
divided the trees between themselves in such a way that the first one got
trees number 1, 4 and 5 and the second one got trees number 2, 3, 6, 7 and
8. As a result, they got such sequence of numbers on the plaques:
8, 7, 1, 6, 4, 3, 5, 2 (the first one planted the trees in the increasing
order and the second one planted the trees in the decreasing order).
Vova wrote down all numbers on the plaques in the order, in which the
trees were planted and wanted to determine which trees were planted by the
first worker and which trees were planted by the second one. Help him to do
this.
Input
The first line contains an integer n that is the number of trees (3 ≤ n ≤ 100 000).
The second line contains n distinct integers between 1 and
n describing the number permutation Vova wrote.
Output
Print in the first line two integers between 1 and (n − 1) that are
the number of trees the first and the second worker planted,
respectively. In the second line print the numbers of the trees planted
by the first worker, in the third line print the number of the trees
planted by the second worker. The numbers must follow in the order, in
which the worker planted these trees. If there are multiple solutions, you
may print any of them. If there's no solution, print “Fail”.
Samples
input | output |
---|
8
8 7 1 6 4 3 5 2
| 3 5
1 4 5
8 7 6 3 2
|
6
3 5 1 2 6 4
| 3 3
3 5 6
1 2 4
|
6
3 5 2 1 6 4
| Fail
|
Problem Author: Sergey Pupyrev
Problem Source: Open Ural FU Personal Contest 2013