Maximum Sum of Selected Magic Values

You are given a sequence of N books arranged in a row, each with an associated magic value. Your task is to partition the sequence into exactly L contiguous segments. The score of a segment is defined as the maximum magic value in that segment. Find the partition that maximizes the sum of these scores and output the result modulo \(10^9+9\) (i.e. \(1000000009\)).

Formally, given an array \(a_0, a_1, \dots, a_{N-1}\), you must choose indices to partition the array into exactly L contiguous non-empty segments. If a segment covers indices from \(i\) to \(j\) (inclusive), its contribution is \(\max\{a_i, a_{i+1}, \dots, a_j\}\). Let the sum of contributions be \(S\). Your task is to compute \(S \bmod \; 1000000009\).

Input and Output specifications below follow the standard input and output format.

inputFormat

The first line contains two integers N and L separated by a space, where N is the number of books and L is the number of segments to select.

The second line contains N space-separated integers representing the magic values of the books.

outputFormat

Output a single integer, which is the maximum possible sum of the scores of the selected segments, taken modulo \(1000000009\).

6 2
1 2 3 4 5 6

11