# Hill Sequence HILLSEQ Solution Codechef

## Hill Sequence HILLSEQ Solution

A sequence A1,A2,…,AN of length N is called good if any one of the following hold:

• The sequence is strictly increasing, or
• The sequence is strictly decreasing, or
• There exists an index i(1
• Aj < Aj +1, for each 1<=j<i
• Aj > Aj +1, for each i<=j<N

For example, the sequences [3,5,9], [2,1], [5,7,4,1] are good, while [6,7,7], [5,2,3] are not.

You are given an array A consisting of N integers. Find a good sequence by rearranging the elements of the array A or report that this is impossible. If there are multiple good sequences, print the lexicographically largest one.

If two sequences A and B have the same length N, we say that A is lexicographically larger than B if there exists an index ii, (1≤i≤N) such that A1=B1,A2=B2,…,Ai−1=Bi−1 and Ai>Bi.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N, denoting the length of the array.
• The second line contains N space-separated integers A1,A2,…,AN, denoting the given array.

Output Format

For each test case, if it is not possible to rearrange the given array into a good sequence, print -1. Otherwise, print a single line containing N space-separated integers the lexicographically largest good sequence that can be made.

Constraints

• 1≤T≤103
• 1≤N≤105
• 1≤Ai≤109
• Sum of N over all test cases does not exceed 5⋅105

• Subtask 1 (100 points): Original constraints

Sample Input 1

``````4
3
2 3 5
3
1 1 1
5
5 7 2 1 2
5
1 2 3 2 2``````

Sample Output 1

``````5 3 2
-1
2 7 5 2 1
-1``````

Explanation

Test case 1: The rearrangements of A which are good sequences are: [5,3,2], [3,5,2], [2,3,5], [2,5,3] Among these, [5,3,2] is the lexicographically largest.

Test case 2: There is no way to obtain a good sequence by rearranging the elements of the array A=[1,1,1].

### SOLUTION

Program C++: Hill Sequence HILLSEQ Solution in C++

``````#include<iostream>
#include<map>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--)
{
int n;
bool flag = true;
map<long long int, long long int> lexo;
cin >> n;
for(int i = 0; i<n; i++)
{
int temp;
cin >> temp;
lexo[temp]++;
}

for(auto x: lexo)
{
auto j = lexo.rbegin();
if(j->second ==2)
{
cout << "-1\n";
flag = false;
break;
}
else if(x.second > 2)
{
cout << "-1\n";
flag = false;
break;
}
}

if(flag == true)
{
for(auto x: lexo)
{
if(x.second==2) cout << x.first << " ";
}
for(auto k = lexo.rbegin(); k!=lexo.rend(); k++)
{
cout << k->first << " ";
}
cout << endl;
}

}
}``````

Program Python: Hill Sequence HILLSEQ Solution in Python

``````t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
q,w,d,x,y=[],[],{},0,0
for i in a:
if i in d:
d[i]+=1
q.append(i)
else:
d[i]=1
w.append(i)
x=max(x,i)
for k,v in d.items():
if v>2:
y=v
break
if d[x]>1 or y>2:
print(-1)
else:
q.sort()
w.sort(reverse=True)
ans=q+w
print(*ans)
``````

## November Long Challenge 2021 Solution

### 2 thoughts on “Hill Sequence HILLSEQ Solution Codechef”

1. There is minor mistake in while condition 🐱.

• 