## Editorial for COCI '07 Contest 1 #5 Srednji

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**One obvious observation is that if the median of subsequence is then the subsequence contains .

For a subsequence , we define a function as the difference of elements greater than and elements smaller than . Thus is the median of if and only if contains and .

Furthermore, if we split into subsequences – part that is left of and – part that is right of , then has median if .

This leads to the following algorithm:

For each subsequence ending with we calculate the delta function and store the number of subsequences having delta value of in .

For each subsequence starting with we calculate the delta function and store the number of subsequences having delta value of in .

To obtain the solution for each value from , we sum .

## Comments