# Hill Sequence HILLSEQ Solution Codechef

Page Contents

## Hill Sequence HILLSEQ Solution

A sequence A1,A2,…,ANA1,A2,…,AN of length NN 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<i<N)i(1<i<N) such that:
• Aj<Aj+1Aj<Aj+1, for each 1≤j<i1≤j<i
• Aj>Aj+1Aj>Aj+1, for each i≤j<Ni≤j<N

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

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

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

### Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains an integer NN, denoting the length of the array.
• The second line contains NN space-separated integers A1,A2,…,ANA1,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−1. Otherwise, print a single line containing NN space-separated integers – the lexicographically largest good sequence that can be made.

### Constraints

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

• Subtask 1 (100 points): Original constraints

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

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

### Explanation

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

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

Hill Sequence HILLSEQ Solution is updated. Click Below

## SOLUTION

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

Note: Solution Credit to Innovative Idea

```#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)
```

## Codechef Long ChallengesSolution

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

1. There is minor mistake in while condition 🐱.

• 