## 快排

// QuickSort returns a sorted slice
func QuickSort(arr []int) {
if len(arr) <= 1 {
return
}
left, right := 0, len(arr)-1
for left < right {
if arr[left+1] > arr[left] {
arr[left+1], arr[right] = arr[right], arr[left+1]
right--
} else {
arr[left+1], arr[left] = arr[left], arr[left+1]
left++
}
}
QuickSort(arr[:left])
QuickSort(arr[left+1:])
}


Time Limit: 2 Seconds      Memory Limit: 65536 KB

##Description
Recently, LBH is learning the curse linear algebra. Thus he is very interested in matrix and determinant now. In order to practice his ability of solving the problem of linear algebra, he just invent some problems by himself. Once the problems was create, he would solve it immediately. However, he meet a problem that was so hard that he couldn’t work out even though racked his brains. The problem was described as follow:

To a integer martix Mnn(aij), we define two function add(Mnn(aij))=Mnn(aij + 1) and sub(Mnn(aij))=Mnn(aij - 1) which were exactly like this:

a串： 110110110，则：

b`串：1011<——这里才是原来b串的头。但是向上对应到a串时，已经是m-1这个位置了。所以说，小于m-1的卷积是没有意义的。

##Description
The people of Absurdistan discovered how to build roads only last year. After the discovery, every city
decided to build their own road connecting their city with another city. Each newly built road can be
used in both directions.

Absurdistan is full of surprising coincidences. It took all N cities precisely one year to build their
roads. And even more surprisingly, in the end it was possible to travel from every city to every other
city using the newly built roads.

##description
Emperor Palpatine has been ruling the Empire for 25 years and Darth Vader has been the head of the Empire Armed Forces. However, the Rebel movement is strong like it never used to be. One of the rebel leaders, Princess Leia from Alderaan, managed to get hold of secret blueprints of the Death Star, the imperial war station.

The Princess was going to deliver the station plan to the secret base for further analysis and searching for vulnerable spots. But her ship was attacked by the space destroyer “Devastator” headed by Darth Vader. At the last moment Princess Leia managed to send her findings to one of the closest planet called Tatooine with her droid R2-D2. Quite conveniently, an old friend of her father Obi-Wan Kenobi lives on that planet.