\(A_i\) を降順にソートして \(2\) 番目の値がもともとあった位置が答えです。ソートした後に元の位置を得るには、 \(A_i\) をソートする代わりに \((A_i,i)\) というタプルをソートすればよいです。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<pair<int,int>>v;
	for(int i=0;i<n;i++){
		int a;
		cin >> a;
		v.push_back(make_pair(a,i+1));
	}
	sort(v.begin(),v.end(),greater<pair<int,int>>());
	
	cout << v[1].second << endl;
}

実装例(Python)

N=int(input())
A=list(map(int,input().split()))
v=[]

for i in range(N):
	v.append((A[i],i+1))

v.sort()
v.reverse()
print(v[1][1])

別解として、前から順に大きい方の値2つとその位置を保持しておくことで、ソートすることなく \(O(N)\) で解くこともできます。(挿入ソートの先頭2つだけを持っておくイメージです)

実装例(Python)

N=int(input())
A=list(map(int,input().split()))

M1,M2=(0,0),(0,0)
for i in range(N):
	X=(A[i],i+1)
	if X>M1:
		M2=M1
		M1=X
	elif X>M2:
		M2=X

print(M2[1])