시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 23 3 2 40.000%

문제

길이 N의 배열 A와 정수 M이 있고. 지학이는 다음과 같은 프로그램을 짰다.

for i<-1 to M do 
    for j<-i+1 to N do  
        if A[i]>A[j] then 
            swap(A[i],A[j])

지학이는 이 프로그램에서 swap 함수가 몇번 작동되는지 궁금해서 여러분을 찾았다. 몇번 작동하는가?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스에는 다음과 같은 정보들이 주어진다.

첫 번째 줄에 자연수 N, M이 주어진다. (N, M < 105)

두 번째 줄에 배열 A의 원소가 주어진다. (-109 ≤ Ai ≤ 109)

출력

각 테스트 케이스마다 교환 횟수를 한 줄에 출력하라.

예제 입력 1

3 3
2 1 3
4 1
3 2 -1 -10

예제 출력 1

1
3
W3sicHJvYmxlbV9pZCI6IjExMDI3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDUwXHVkNjU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzQgTlx1Yzc1OCBcdWJjMzBcdWM1ZjQgQVx1YzY0MCBcdWM4MTVcdWMyMTggTVx1Yzc3NCBcdWM3ODhcdWFjZTAuIFx1YzljMFx1ZDU1OVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM5ZjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmZvciBpJmx0Oy0xIHRvIE0gZG8gXHJcbiAgICBmb3IgaiZsdDstaSsxIHRvIE4gZG8gIFxyXG4gICAgICAgIGlmIEFbaV0mZ3Q7QVtqXSB0aGVuIFxyXG4gICAgICAgICAgICBzd2FwKEFbaV0sQVtqXSlcclxuPFwvcHJlPlxyXG5cclxuPHA+XHVjOWMwXHVkNTU5XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgc3dhcCBcdWQ1NjhcdWMyMThcdWFjMDAgXHViYTg3XHViYzg4IFx1Yzc5MVx1YjNkOVx1YjQxOFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWMxMWMgXHVjNWVjXHViN2VjXHViZDg0XHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YjJlNC4gXHViYTg3XHViYzg4IFx1Yzc5MVx1YjNkOVx1ZDU1OFx1YjI5NFx1YWMwMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWJjZjRcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggTiwgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChOLCBNICZsdDsgMTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMzBcdWM1ZjQgQVx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwPHN1cD45PFwvc3VwPiAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWQ1MFx1ZDY1OCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEwMjciLCJwcm9ibGVtX2xhbmciOiI2IiwidGl0bGUiOiJTXHUxZWFlUCBYXHUxZWJlUCIsImRlc2NyaXB0aW9uIjoiPHA+Q2hvIGQmYXRpbGRlO3kgc1x1MWVkMSBuZ3V5JmVjaXJjO24gYTEsIGEyLCAuLi4sIGFOIHYmYWdyYXZlOyBzXHUxZWQxIG5ndXkmZWNpcmM7biBNLiBYJmVhY3V0ZTt0IHRodVx1MWVhZHQgdG8mYWFjdXRlO24gXHUwMTExXHUwMWIwYSBNIHNcdTFlZDEgbmhcdTFlY2YgbmhcdTFlYTV0IHZcdTFlYzEgXHUwMTExXHUxZWE3dSBkJmF0aWxkZTt5IG5oXHUwMWIwIHNhdTo8XC9wPlxyXG5cclxuPHByZT5cclxuZm9yIGkmbHQ7LTEgdG8gTSBkbyBcclxuICAgIGZvciBqJmx0Oy1pKzEgdG8gTiBkbyBcclxuICAgICAgICBpZiBhW2ldJmd0O2Fbal0gdGhlbiBcclxuICAgICAgICAgICAgc3dhcChhW2ldLGFbal0pPFwvcHJlPlxyXG5cclxuPHA+VHJvbmcgXHUwMTExJm9hY3V0ZTsgc3dhcCBsJmFncmF2ZTsgaCZhZ3JhdmU7bSBcdTAxMTFcdTFlZDVpIGdpJmFhY3V0ZTsgdHJcdTFlY2IgY1x1MWVlN2EgMiBiaVx1MWViZm4gY2hvIG5oYXUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNobyBzXHUxZWQxIG5ndXkmZWNpcmM7biBNIHYmYWdyYXZlOyBkJmF0aWxkZTt5IHNcdTFlZDEgbmd1eSZlY2lyYztuIGExLCBhMiwgLi4uLCBhTi4gSCZhdGlsZGU7eSBcdTAxMTFcdTFlYmZtIHNcdTFlZDEgbFx1MWVhN24gdGhcdTFlZjFjIGhpXHUxZWM3biBoJmFncmF2ZTttIHN3YXAgc2F1IGtoaSB0aHVcdTFlYWR0IHRvJmFhY3V0ZTtuIGtcdTFlYmZ0IHRoJnVhY3V0ZTtjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+R1x1MWVkM20gbmhpXHUxZWMxdSBiXHUxZWQ5IGRcdTFlZWYgbGlcdTFlYzd1LiBWXHUxZWRiaSBtXHUxZWQ3aSBiXHUxZWQ5IGRcdTFlZWYgbGlcdTFlYzd1OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkQmb2dyYXZlO25nIDE6IEhhaSBzXHUxZWQxIG5ndXkmZWNpcmM7biBkXHUwMWIwXHUwMWExbmcgTiB2JmFncmF2ZTsgTSB2XHUxZWRiaSAwICZsdDsgTiwgTSAmbHQ7IDEwPHN1cD41PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5EJm9ncmF2ZTtuZyAyOiBOIHNcdTFlZDEgbmd1eSZlY2lyYztuIHRoXHUxZWMzIGhpXHUxZWM3biBkJmF0aWxkZTt5IGEsIG1cdTFlZDdpIHNcdTFlZDEgYyZhYWN1dGU7Y2ggbmhhdSAmaWFjdXRlO3QgbmhcdTFlYTV0IDEgZFx1MWVhNXUgYyZhYWN1dGU7Y2guIC0xMDxzdXA+OTxcL3N1cD4gJmxlOyBhaSAmbGU7IDEwPHN1cD45PFwvc3VwPi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1MWVlOG5nIHZcdTFlZGJpIG1cdTFlZDdpIHRlc3QsIGluIHJhIDEgZCZvZ3JhdmU7bmcgZHV5IG5oXHUxZWE1dCBjaFx1MWVlOWEgc1x1MWVkMSBsXHUxZWE3biB0aFx1MWVmMWMgaGlcdTFlYzduIGgmYWdyYXZlO20gc3dhcCB0aGVvIHkmZWNpcmM7dSBjXHUxZWE3dSBiJmFncmF2ZTtpIHRvJmFhY3V0ZTtuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHViY2EwXHVkMmI4XHViMGE4XHVjNWI0In1d