Арсен мен Чингиз — аты аңызға айналған Учиха кланының мүшелері.

Саяси келіспеушіліктерге байланысты оларға бүкіл кланды \(k\) бос емес бөлікке бөлуді тапсырды. Кланды \(n\) адамнан тұратын массив ретінде қарастыруға болады, мұнда \(a_i\) — \(i\)-нөмірлі адамның күші.

Клан бірнеше қосалқы кесіндіге бөлінді делік. Бөлудің құны барлық қосалқы кесінділердегі күштер инверсияларының жалпы саны ретінде есептеледі.

Инверсия деп массивтегі тәртіптелген жұпты \((i, j)\) айтамыз, мұнда \(i < j\) және \(a_i > a_j\).

Мысалы, \([5, 2, 3, 1, 5, 4]\) массивін қарастырайық және оны келесі қосалқы кесінділерге бөлейік: \([5, 2, 3], [1, 5, 4]\).

Бірінші қосалқы кесіндідегі инверсиялар: \((5,2)\), \((5,3)\). Екінші қосалқы кесіндідегі инверсия: \((5,4)\). Жалпы бөлудің құны: \(2 + 1 = 3\).

Мәселені қызықтырақ ету үшін, \(q\) сұранысқа жауап беру қажет. Әр сұраныс екі санмен беріледі: \(L, R\).

Сандық массивтің \([L, R]\) қосалқы кесіндісі үшін \(k\) бос емес қосалқы кесінділерге бөлу нұсқаларының ішінде ең аз мүмкін болатын бөліну құнын табыңыз.

Сіздің тапсырмаңыз — әр сұранысқа дұрыс жауап беру.

Енгізу

Бірінші жолда бос орын арқылы екі бүтін сан \(n\) және \(k\) берілген – кландағы адамдар саны және кланды бөлу керек бөліктер саны (\(1 \le n \le 2000\); \(1 \le k \le n\)).

Екінші жолда \(n\) бүтін сан берілген: \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 10^9)\).

Үшінші жолда бүтін сан \(q\) \((1 \le q \le 2 \cdot 10^5)\) – сұраныстар саны берілген. Келесі \(q\) жолда сұраныстар сипатталған.

Әр сұраныс \(L, R\)(\(1 \le L \le R \le n, R - L + 1 \ge k\)) түрінде беріледі – \([L, R]\) ішкі бөлігін \(k\) бос емес бөлікке бөлудің ішіндегі ең арзанының құнын табу керек.

Шығару

Әр сұраныс үшін жауапты жеке жолға шығарыңыз.

Мысалдар

Енгізу 1

9 4
8 5 4 2 6 8 9 1 5
1
1 8

Жауап 1

1

Енгізу 2

19 2
15 9 13 10 9 15 5 12 10 1 8 19 2 11 20 4 12 10 6
8
9 16
16 18
14 18
3 17
2 17
16 17
1 3
13 14

Жауап 2

4
0
1
21
22
0
0
0

Ескертпелер

Бірінші мысалда біз \([8,5,4,2,6,8,9,1]\) подмассивін келесі бөліктерге бөле аламыз: \([8],[5],[4,2,6,8,9],[1]\). Құны = \(0 + 0 + 1 + 0 = 1\) болады.