foo.cpp

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <complex>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <queue>
#include <bitset>

using namespace std;
using namespace __gnu_cxx;

typedef unsigned long long ullong;
typedef long long llong;
typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
                                it != adj[v].end(); ++it)
#define FOR(v, it) for (auto it = v.begin(); it != v.end(); ++it)


int main() {
  int n;
  while (scanf("%d", &n) != EOF) {
    vector<int> vec;
    vec.reserve(2*n);
    for (int i = 0; i < n; ++i) {
      int x;
      scanf("%d", &x);
      vec.push_back(x);
    }
    for (int i = 0; i < n; ++i) {
      vec.push_back(vec[i]);
    }
    for (int i = 0; i < 2*n; ++i) {
      vec[i] -= i;
    }
    multiset<int> mset;
    for (int i = 0; i < n; ++i) {
      if (vec[i] <= 0) {
        mset.insert(vec[i]);
      }
    }
    ullong best = mset.size();
    int best_idx = 0;
    for (int i = 1; i < n; ++i) {
      if (vec[i+n-1] <= -i) {
        mset.insert(vec[i+n]);
      }
      auto it = mset.find(vec[i-1]);
      if (it != mset.end()) {
        mset.erase(it);
      }
      while (mset.size() && *mset.rbegin() > -i) {
        mset.erase(*mset.rbegin());
      }
      if (mset.size() > best) {
        best = mset.size();
        best_idx = i;
      }
    }
    #ifdef DEBUG
    printf("best: %llu\n", best);
    #endif
    printf("%d\n", best_idx+1);
  }
  return 0;
}