306449: CF1199A. City Day

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

City Day

题意翻译

### 题目描述 很多年了,N市的节日是在下雨天最严重的那一天举行。新的领导者打算去打破这个传统,并准备选择一个下雨天不是那么严重的一天进行活动。领导者知道$n$天的天气预报。在第$i$天上,下$a_i$毫米的雨。 领导者知道市民们关注$x$天前以及$y$天后的天气。因此,他说假定第$d$天下雨不是那么严重在满足以下情况 1. 满足$a_d<a_j$ 2. $j$满足$d-x \leq j<d$或者$d<j \leq d+y$ 由于市民们只看n天,所以j同时还要满足$1 \leq j \leq n$ 请帮助领导者找到下雨不是那么严重的一天 ### 输入格式 第一行输入$n$,$x$,$y$,他们满足$1 \leq n \leq 100000$, $0 \leq x,y \leq 7$ 第二行输入$a_1$,$a_2$,...,$a_n$,他们满足$1 \leq a_i \leq 10^9$ ### 输出格式 输出最早的下雨不是那么严重的一天 ### 说明/提示 #### 第一个样例 第3天和第8天都满足这个条件,第三天更早,所以答案是第三个。 #### 第二个样例 第三天不满足这个条件,因为$3+y=6$ 且 $a_3>a_6$。第8天是答案。请注意:$8+y=11$,然而我们没有第11天,所以无需考虑第11天。

题目描述

For years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the $ n $ days of summer. On the $ i $ -th day, $ a_i $ millimeters of rain will fall. All values $ a_i $ are distinct. The mayor knows that citizens will watch the weather $ x $ days before the celebration and $ y $ days after. Because of that, he says that a day $ d $ is not-so-rainy if $ a_d $ is smaller than rain amounts at each of $ x $ days before day $ d $ and and each of $ y $ days after day $ d $ . In other words, $ a_d < a_j $ should hold for all $ d - x \le j < d $ and $ d < j \le d + y $ . Citizens only watch the weather during summer, so we only consider such $ j $ that $ 1 \le j \le n $ . Help mayor find the earliest not-so-rainy day of summer.

输入输出格式

输入格式


The first line contains three integers $ n $ , $ x $ and $ y $ ( $ 1 \le n \le 100\,000 $ , $ 0 \le x, y \le 7 $ ) — the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after. The second line contains $ n $ distinct integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ denotes the rain amount on the $ i $ -th day.

输出格式


Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.

输入输出样例

输入样例 #1

10 2 2
10 9 6 7 8 3 2 1 4 5

输出样例 #1

3

输入样例 #2

10 2 3
10 9 6 7 8 3 2 1 4 5

输出样例 #2

8

输入样例 #3

5 5 5
100000 10000 1000 100 10

输出样例 #3

5

说明

In the first example days $ 3 $ and $ 8 $ are not-so-rainy. The $ 3 $ -rd day is earlier. In the second example day $ 3 $ is not not-so-rainy, because $ 3 + y = 6 $ and $ a_3 > a_6 $ . Thus, day $ 8 $ is the answer. Note that $ 8 + y = 11 $ , but we don't consider day $ 11 $ , because it is not summer.

Input

题意翻译

### 题目描述 很多年了,N市的节日是在下雨天最严重的那一天举行。新的领导者打算去打破这个传统,并准备选择一个下雨天不是那么严重的一天进行活动。领导者知道$n$天的天气预报。在第$i$天上,下$a_i$毫米的雨。 领导者知道市民们关注$x$天前以及$y$天后的天气。因此,他说假定第$d$天下雨不是那么严重在满足以下情况 1. 满足$a_d<a_j$ 2. $j$满足$d-x \leq j<d$或者$d<j \leq d+y$ 由于市民们只看n天,所以j同时还要满足$1 \leq j \leq n$ 请帮助领导者找到下雨不是那么严重的一天 ### 输入格式 第一行输入$n$,$x$,$y$,他们满足$1 \leq n \leq 100000$, $0 \leq x,y \leq 7$ 第二行输入$a_1$,$a_2$,...,$a_n$,他们满足$1 \leq a_i \leq 10^9$ ### 输出格式 输出最早的下雨不是那么严重的一天 ### 说明/提示 #### 第一个样例 第3天和第8天都满足这个条件,第三天更早,所以答案是第三个。 #### 第二个样例 第三天不满足这个条件,因为$3+y=6$ 且 $a_3>a_6$。第8天是答案。请注意:$8+y=11$,然而我们没有第11天,所以无需考虑第11天。

加入题单

上一题 下一题 算法标签: