SAS001  Apoorv and Maximum Inversion
Apoorv has an array of n integers.Inversion count of an array is defined by number of pair of indices(i,j) such that i<j and arr[i]>arr[j] .You are given an integer p.Apoorv has to find the subarray with maximum inversion count among all subarrays of size p.Apoorv find this job very tough so he turns to you for help.
Constraints :
1<=n<=500000
1000000000<=arr[i]<=1000000000
1<=p<=n
Input
First line contains two integers n and p.
Next line contains n space separated integers denoting the elements of the array.
Output
Output two space separated integers first integer should be the starting index (1based indexing) of the subarray and next integer would be the count of inversions in that subarray.In case there is a tie in maximum inversion count print the smallest starting index among the subarrays having maximum inversion count.
Example
Input: 10 5 15 51 44 44 76 50 29 88 48 50 Output: 5 6
hide comments
ayush926:
20180317 11:48:04
Nice question!


shuvam_kedia:
20180316 19:59:52
Nice problem :) sas1905 _/\_ 

amit_ranjan:
20171231 11:51:09
My 175 on spoj :) 

jaideeppyne:
20171025 18:17:36
Segment tree + sliding window... try the problem "Inversion Count" in SPOJ before solving this.. that will be of great help ..HAPPY CODING! :D 

divyanshjr:
20170813 18:53:16
sas pro! Nice problem.. :) 

choudharymohit:
20170812 18:24:08
Sas pro!! _/\_


siddharth_0196:
20170812 13:40:09
Nice question! Sas pro! _/\_


yogahmad:
20170812 05:05:55
Nice problem :) 

akt_1998:
20170811 20:09:55
Nice one ;) 

aman224:
20170811 19:37:15
Awesome problem :D

Added by:  sas1905 
Date:  20170811 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 