A - Temperature Outliers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は気象観測の研究をしています。ある地域に設置された N 個の観測地点で、同じ日の最高気温を記録しました。観測地点には 1 から N までの番号が付けられており、観測地点 i (1 \leq i \leq N) で記録された最高気温は A_i ℃でした。

高橋君は、記録された気温の中に平均値から大きく離れた観測地点がないかを調べたいと考えています。具体的には、全観測地点の気温の平均値を

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

としたとき、各観測地点 i について |A_i - \mu|（気温と平均値の差の絶対値）を求め、この値が最も大きい観測地点の番号を出力してください。

そのような観測地点が複数ある場合は、番号が最も小さいものを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -100 \leq A_i \leq 100
  • N は整数
  • A_i は整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、観測地点の数を表す整数 N が与えられる。
  • 2 行目には、各観測地点の気温を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

平均値からの差の絶対値が最も大きい観測地点の番号を 1 行で出力せよ。該当する観測地点が複数ある場合は、番号が最も小さいものを出力せよ。

入力例 1

5
20 22 21 35 23

出力例 1

4

入力例 2

7
10 12 11 13 10 -5 11

出力例 2

6

入力例 3

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

出力例 3

10

Score : 233 pts

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

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of observation stations.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the temperature at each observation station.

Output

Output in one line the number of the observation station with the largest absolute difference from the average. If there are multiple such observation stations, output the one with the smallest number.

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