New Year Chaos

It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by  from  at the front of the line to  at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if and  bribes , the queue will look like this: .

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

Function Description

Complete the function minimumBribes in the editor below. It must print an integer representing the minimum number of bribes necessary, or Too chaotic if the line configuration is not possible.

minimumBribes has the following parameter(s):

• q: an array of integers

Input Format

The first line contains an integer , the number of test cases.

Each of the next  pairs of lines are as follows: 
- The first line contains an integer , the number of people in the queue 
- The second line has  space-separated integers describing the final state of the queue.

Constraints

Subtasks

For  score 
For  score 

Output Format

Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than  people.

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Sample Output

3
Too chaotic

Explanation

Test Case 1

The initial state:

After person  moves one position ahead by bribing person :

Now person  moves another position ahead by bribing person :

And person  moves one position ahead by bribing person :

So the final state is  after three bribing operations.

Test Case 2

No person can bribe more than two people, so its not possible to achieve the input state.

---

생각보다 까다롭다. Medium 이상의 문제들은 문제에 제시된 처리 원리를 그대로 구현하기 보다는, 문제의 핵심 원리를 파악하여 그것을 로직으로 구현해야 한다. 이 문제에서도 Chaos 상황이 bride로 만들어 질 수 없는 상황이라고 했는데, 그러면 그걸 어떻게 알지? 에서 생각이 시작되어야 했다.

Chaos인 상황...Bride의 원칙을 다시 살펴보면 한 사람당 최대 2회만 bribe가 가능하다고 했으니, 앞 사람과 두 번의 bribe를 했다면 뒷 사람과 최대 2의 차이가 나게 되며, 3 이상의 값은 나올 수 없다는 얘기이다. 또 다른 원칙 중 하나는 앞 사람 하고만 bribe가 가능하다는 것이다. 즉, 맨 앞 사람은 기회가 없으며, 두번째는 1번의 기회만 있다.

이런 내용을 깔끔하게 로직화 하는 것은....참...어렵다....ㅠ