解题思路

• 将过程按“转一圈”为一个批次（轮）。

  • 若玩家数 m ≤ n：每一圈只能坐满前 m 个吊舱，且同一批玩家每圈固定坐吊舱 1..m。连续 L 圈后，第 p(1..m) 位玩家总幸福值为 L * h_p。答案就是前 m 个吊舱幸福值的最大者（并取最靠前下标）。

  • 若玩家数 m > n：每圈恰有 n 人上车，队列整体向后旋转 n 位。把所有上车时刻按时间线排成 T = n * L 次“座位事件”。第 j(0..T-1) 次事件使用的吊舱是 (j mod n) + 1，被安排的玩家是“队列中的第 j 位”（跨圈连续计数）。于是第 p 位玩家的上车时刻是所有 j ≡ p-1 (mod m) 且 0 ≤ j < T。

    • 因而第 p 位玩家上车次数

题目内容

多多来到游乐场坐摩天轮，摩天轮共有 $n$ 个吊舱，包括多多在内总共即将有 $m$ 名玩家排队，每个吊舱最多只能坐一名玩家，每名玩家游玩结束后会到队尾继续排队。每当有一名玩家离开吊舱，下一名排在队首的玩家会立即坐上这个空吊舱，在游玩过程中不会有玩家加入也不会有玩家离开。

第 $i$ 个吊舱的幸福指数为 $h_i$ ，坐到该吊舱的人会获得 $h_i$ 点幸福指数，多多提前掌握了现场的排队人数以及每个吊舱的幸福指数，他想在摩天轮转 $L$ 圈后获得最高的总幸福指数，问他需要抢到队伍中的第几个位置?如果多个位置的总幸福指数一样，多多想排到尽可能靠前的位置。

输入描述

第一行为三个正整数 $n,m,L(1≤n,m≤10^5,1≤L≤10^9)$

第二行为 $n$ 个整数 $h_1,h_2,...,hn (1≤h_i≤10^9)$

输出描述

输出队伍中幸福指款最高的位置，若存在多个位置满足条件，输出最靠前的那个位置。

补充说明

对于 $60$%的数据 , $1≤n,m,L≤1000$

对于 $100$%的数据，$1≤n,m≤10^5,1≤L≤10^9,1≤h_i≤10^9$

样例1

输入

5 3 1000000000
1 2 3 4 5

输出

3

说明

$5$ 个吊舱 $3$ 名玩家，每一轮都只能坐满前 $3$ 个吊舱的位置，且 $3$ 个位置的幸福指数总是 $1,2,3$ ，经过 $10^9$ 轮后，玩家的幸福指教分别为 $1 ×10^9,2 × 10^9,3× 10^9$ ，最终第 $3$ 个位置的幸福指数最高。

样例2

输入

3 6 2
2 3 1

输出

2

说明

$3$ 个吊舱 $6$ 名玩家，第一轮玩家 $1,2,3$ 坐上摩天轮，分别获得幸福指数 $2,3,1$，第二轮玩家 $4,5,6$ 坐上摩天轮，分别获得幸福指数 $2,3,1$，$2$ 轮过后第 $2$ 名与第 $5$ 名玩家都获得 $3$ 点幸福指数，取最小序号的位置 $2$ 输出答案。