# Two progressions CodeForce 125D 思维题

An arithmetic progression is such a non-empty sequence of numbers where the difference between any two successive numbers is constant. This constant number is called common difference. For example, the sequence 3, 7, 11, 15 is an arithmetic progression. The definition implies that any sequences whose length equals 1 or 2 are arithmetic and all sequences whose length equals 0 are non-arithmetic.

You are given a sequence of
different integers
a
1
,  a
2
, …,  a
n

. You should either split it into two arithmetic progressions or find out that the operation is impossible to perform. Splitting assigns each member of the given sequence to one of two progressions, but the relative order of numbers does not change. Splitting is an inverse operation to merging.

Input

The first line contains a positive integer
n
(
2 ≤  n
≤ 30000),
n
is the length of the given sequence. The second line contains elements of the given sequence
a
1
,  a
2
, …,  a
n

(
- 10 8
≤  a
i

≤ 10 8
). The elements of the progression are different integers.

Output
Print the required arithmetic progressions, one per line.
The progressions can be positioned in any order. Each progression
should contain at least one number. If there’s no solution, then print
“No solution” (without the quotes)in the only line of the input file. If
there are several solutions, print any of them.
Examples

Input
Output

Input

5
1 2 3 -2 -7

Output

1 2 3
-2 -7

Note
In the second sample another solution is also possible (number three can be assigned to the second progression): 1, 2 and 3, -2, -7.

OJ-ID：
CodeForce 125D
author：
Caution_X
date of submission：
20191002
tags：

description modelling：

(1) 对每个数，要么在第一个子序列，要么在第二个子序列，根据鸽巢原理，将前三个元素放入两个数列必然有两个数在同一个数列，其中元素个数大于1的数列会形成一个公差，且公差d最多只有有三个值
(2) 根据其中一个公差d生成一个等差数列，然后将剩下的数放在另一个数列，判断另一个数列是不是等差数列
(3) 是等差数列则直接输出，否则将第一个数列尾部元素移到第二个数列，判断是否构成等差数列
(4) 如果构成则输出，否则枚举其他公差值

AC CODE:

#include
using namespace std;
int a[30005],n;
bool vis[30005];
void print(vector v)
{
for(int i=0; i<v.size(); i++)    printf("%d ",v[i]);
printf("\n");
}
bool check(vector v)
{
if(v.empty())    return false;
else if(v.size()==1||v.size()==2)    return true;
int d=v[1]-v[0];
for(int i=1; i<v.size(); i++) {
if(v[i]-v[i-1]!=d)    return false;
}
return true;
}
bool solve(int l,int r)
{
vector v1,v2;
int d=a[r]-a[l],get=a[l],last=-1;
for(int i=0; i<=n; i++)    vis[i]=false;
for(int i=1; i<=n; i++) {
if(a[i]==get) {
get+=d;
v1.push_back(a[i]);
last=i;
} else {
vis[i]=true;
}
}
for(int i=1; i<=n; i++) {
if(vis[i]) {
v2.push_back(a[i]);
}
}
if(check(v2)) {
print(v1);
print(v2);
return true;
} else {
v1.pop_back();
v2.clear();
vis[last]=true;
for(int i=1; i<=n; i++) {
if(vis[i])
v2.push_back(a[i]);
}
if(check(v2)) {
print(v1);
print(v2);
return true;
}
}
return false;
}
int main()
{
//freopen("input1.txt","r",stdin);
//freopen("input2.txt","r",stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++)    {
scanf("%d",&a[i]);
}
if(n==2)    printf("%d\n%d",a[1],a[2]);
else if(!solve(1,2)&&!solve(1,3)&&!solve(2,3))    printf("No solution\n");
return 0;
}