Problem Statement

Takahashi is conducting research on weather observation. He recorded the daily high temperature on the same day at N observation stations set up in a certain region. The observation stations are numbered from 1 to N, and the high temperature recorded at observation station i (1 \leq i \leq N) was A_i ℃.

Takahashi wants to check whether any observation station recorded a temperature that deviates significantly from the average. Specifically, let the average temperature across all observation stations be

\mu = \frac{A_1 + A_2 + \cdots + A_N}{N}

For each observation station i, compute |A_i - \mu| (the absolute difference between the temperature and the average), and output the number of the observation station for which this value is the largest.

If there are multiple such observation stations, output the one with the smallest number.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -100 \leq A_i \leq 100
• N is an integer
• A_i is an integer

Sample Input 1

5
20 22 21 35 23

Sample Output 1

4

Sample Input 2

7
10 12 11 13 10 -5 11

Sample Output 2

6

Sample Input 3

10
30 31 29 30 32 31 30 29 31 -10

Sample Output 3

10

Problem Statement

Takahashi is working as a receptionist for a secret club. To enter the club, a member's message must contain the correct password hidden within it.

Today, N people wish to enter the club, and each of them has sent one message. The message from the i-th person is a string S_i consisting of lowercase English letters.

The club's password is sayounara. If the string S_i contains sayounara as a subsequence, that person is considered to know the correct password and is permitted to enter.

Here, a string T is a subsequence of a string S means that by removing zero or more characters from S and concatenating the remaining characters in their original order, we obtain T. (The removed characters do not need to be contiguous.)

For each of the N messages, determine whether it contains the password.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq |S_i| \leq 5 \times 10^6
• S_i is a string consisting of lowercase English letters
• \displaystyle\sum_{i=1}^{N} |S_i| \leq 5 \times 10^6

Sample Input 1

3
sayounara
xsxaxxyxouxnxaxrxa
sayounarasayounara

Sample Output 1

Yes
Yes
Yes

Sample Input 2

4
sayonara
aranouyas
hello
saaayyyy

Sample Output 2

No
No
No
No

Sample Input 3

6
sayounara
abcdsaefgayhibjkoulmnnopaaqrsata
sayonara
ssssaaaayyyyoooouuuunnnnaaarrrraaaa
souynara
aaaaaaaaasaaaaaaaaayaaaaaaaaaaoaaaaaaaaaaauaaaaaaaaaanaaaaaaaaaaaaaaaaaaaaaaraaaaaaaaaa

Sample Output 3

Yes
Yes
No
Yes
No
Yes

Sample Input 4

10
sayounara
abcdefghijklmnopqrstuvwxyz
saeiyounotaruaze
thisisasayounaramessage
saayyyooouuunnnaarrraaa
aaaaranuoyas
ssayyoouunnaarraa
sxaxyzoyounbara
saaaaaaaayoooounaaaaara
ra

Sample Output 4

Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No

Sample Input 5

1
a

Sample Output 5

No

Problem Statement

Takahashi is analyzing meteorological data.

There are N observation stations arranged in a line, and each observation station i (1 \leq i \leq N) has recorded the temperature F_i for the day. Takahashi wants to smooth the data so that the maximum temperature value is less prominent.

In the smoothing process, he selects an integer l (1 \leq l \leq N - K + 1) such that K consecutive stations all fall within the range of observation stations, and groups stations l, l+1, \ldots, l+K-1 together. The temperatures of all stations in the group are simultaneously replaced with the arithmetic mean of the group \displaystyle\frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}. The temperatures of stations not included in the group remain unchanged. This operation is performed exactly once (choosing not to perform the operation is not allowed).

Let F'_1, F'_2, \ldots, F'_N be the temperatures at each station after the operation. That is, for stations i included in the group (l \leq i \leq l+K-1), \displaystyle F'_i = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}, and for all other stations i, F'_i = F_i. Here, the mean is computed exactly as a real number, without truncation or rounding.

Takahashi wants to choose l optimally to minimize the maximum temperature after the operation, \displaystyle\max_{1 \leq i \leq N} F'_i.

Find the minimum possible value of this maximum.

Constraints

• 1 \leq K \leq N \leq 10^6
• -10^9 \leq F_i \leq 10^9
• N, K are integers
• F_i are integers

Sample Input 1

5 2
3 10 4 2 8

Sample Output 1

8.0000000000

Sample Input 2

6 3
-5 0 -2 7 1 -3

Sample Output 2

1.6666666667

Sample Input 3

12 4
15 -3 22 8 7 30 -10 5 18 12 -4 25

Sample Output 3

25.0000000000

Sample Input 4

30 7
100 -50 23 75 -10 200 0 45 90 -80 60 110 -30 15 5 130 -100 70 85 -20 40 95 -60 150 10 -5 55 120 -90 35

Sample Output 4

150.0000000000

Sample Input 5

1 1
-1000000000

Sample Output 5

-1000000000.0000000000

Problem Statement

Takahashi is a city hall employee responsible for managing the street lights on a certain road.

There are N street lights lined up in a row along this road, numbered from left to right as street light 1, street light 2, \ldots, street light N. Each street light i (1 \leq i \leq N) has an integer parameter S_i. This parameter represents the brightness of the street light, but it can be negative for malfunctioning street lights.

Takahashi needs to temporarily turn off street light T in order to replace its bulb. While it is turned off, the brightness of street light T is treated as 0 regardless of its original value S_T.

According to the city's safety standards, for a section consisting of K consecutive street lights, the minimum brightness among all street lights in that section is defined as the "safety level" of that section. A lower safety level means the section is darker and more dangerous.

While street light T is turned off, Takahashi wants to compute the safety level for every section of K consecutive street lights that includes street light T, and determine the maximum value among them.

More precisely, consider all integers l satisfying the following conditions:

• 1 \leq l and l + K - 1 \leq N
• l \leq T \leq l + K - 1 (the section includes street light T)

For each l, the safety level of the section [l, l+K-1] is defined as follows. For each integer i satisfying l \leq i \leq l+K-1, let

A_i = \begin{cases} 0 & (i = T) \\ S_i & (i \neq T) \end{cases}

Then the minimum value among A_l, A_{l+1}, \ldots, A_{l+K-1} is the safety level of this section.

Compute the safety level for all l satisfying the conditions, and output the maximum value among them.

Note that under the given constraints, there always exists at least one l satisfying the conditions.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq K \leq N
• 1 \leq T \leq N
• -10^9 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

5 3 3
2 -1 7 3 1

Sample Output 1

0

Sample Input 2

6 3 4
-5 3 2 10 -3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

-2

Sample Input 4

20 5 12
4 -3 7 2 -1 8 5 -6 3 9 1 100 -2 6 4 -7 3 8 2 -5

Sample Output 4

-2

Sample Input 5

1 1 1
1000000000

Sample Output 5

0