Problem: Gardener Alex loves to grow trees. We remind that tree is a connected acyclic graph on n vertices. 

Today he decided to grow a rooted binary tree. A binary tree is a tree where any vertex has no more than two sons. Luckily, Alex has a permutation of numbers from 1 to n which he was presented at his last birthday, so he decided to grow a tree according to this permutation. To do so he does the following process: he finds a minimum element and makes it a root of the tree. After that permutation is divided into two parts: everything that is to the left of the minimum element, and everything that is to the right. The minimum element on the left part becomes the left son of the root, and the minimum element on the right part becomes the right son of the root. After that, this process is repeated recursively on both parts.

Now Alex wants to grow a forest of trees: one tree for each cyclic shift of the permutation. He is interested in what cyclic shift gives the tree of minimum depth. Unfortunately, growing a forest is a hard and long process, but Alex wants the answer right now. Will you help him?

We remind that cyclic shift of permutation a_1, a_2, …, a_k, …, a_n for k elements to the left is the permutation a_{k + 1}, a_{k + 2}, …, a_n, a_1, a_2, …, a_k.

Input

First line contains an integer number n ~ (1 ⩽ n ⩽ 200 000) — length of the permutation.

Second line contains n integer numbers a_1, a_2, …, a_n ~ (1 ⩽ a_i ⩽ n), and it is guaranteed that all numbers occur exactly one time.

Output

Print two numbers separated with space: minimum possible depth of a tree and how many elements we need to shift left to achieve this depth. The number of elements should be a number from 0 to n - 1. If there are several possible answers, print any of them.

Example

Input


4
1 2 3 4


Output


3 2

Note

The following picture depicts all possible trees for sample test and cyclic shifts on which they are achieved. 

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,mmx,avx,tune=native")
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
template <int _SEGSZ>
class MinSegTree {
 public:
  static const int SEGSZ = _SEGSZ;
  int segn = _SEGSZ;
  pair<int, int> t[2 * SEGSZ];
  const pair<int, int> identity = make_pair(INF, INF);
  pair<int, int> combine(const pair<int, int>& lefts,
                         const pair<int, int>& rights) {
    return min(lefts, rights);
  }
  pair<int, int>& operator[](int idx) { return t[segn + idx]; }
  void init(int n) { segn = n; }
  void build() {
    int n = segn;
    for (int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
  }
  void sset(int p, const pair<int, int>& value) {
    int n = segn;
    for (t[p += n] = value; p >>= 1;) t[p] = combine(t[p << 1], t[p << 1 | 1]);
  }
  int query(int l, int r) {
    if (l > r) return identity.second;
    r++;
    int n = segn;
    pair<int, int> resl = identity, resr = identity;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = combine(resl, t[l++]);
      if (r & 1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr).second;
  }
};
class SegmentTreeFast {
 public:
  int modifyOperation(int x, int y) { return x + y; }
  int queryOperation(int l, int r) { return max(l, r); }
  int deltaEffectOnSegment(int delta, int segmentLength) { return delta; }
  int initNeutralDelta() { return 0; }
  bool isNeutralDelta(int delta) { return delta == 0; }
  int getInitValue(int i) { return 0; }
  int getNeutralValue() { return 0; }
  int joinDeltas(int delta1, int delta2) { return delta1 + delta2; }
  int _cache_neutral_delta;
  int getNeutralDelta() { return _cache_neutral_delta; }
  int* value;
  int* delta;
  int gn;
  int joinValueWithDelta(int value, int delta) {
    if (isNeutralDelta(delta)) return value;
    return modifyOperation(value, delta);
  }
  void pushDelta(int i) {
    int d = 0;
    for (; (i >> d) > 0; d++) {
    }
    for (d -= 2; d >= 0; d--) {
      int x = i >> d;
      value[x >> 1] = joinNodeValueWithDelta(x >> 1, 1 << (d + 1));
      delta[x] = joinDeltas(delta[x], delta[x >> 1]);
      delta[x ^ 1] = joinDeltas(delta[x ^ 1], delta[x >> 1]);
      delta[x >> 1] = getNeutralDelta();
    }
  }
  SegmentTreeFast(int n) {
    _cache_neutral_delta = initNeutralDelta();
    gn = n;
    value = new int[2 * n];
    for (int i = 0; i < n; i++) {
      value[i + n] = getInitValue(i);
    }
    for (int i = n - 1; i > 0; --i)
      value[i] = queryOperation(value[i << 1], value[i << 1 | 1]);
    delta = new int[2 * n];
    fill(delta, delta + (2 * n), getNeutralDelta());
  }
  int joinNodeValueWithDelta(int i, int len) {
    return joinValueWithDelta(value[i], deltaEffectOnSegment(delta[i], len));
  }
  int query(int from, int to) {
    from += gn;
    to += gn;
    pushDelta(from);
    pushDelta(to);
    int resl = getNeutralValue();
    int resr = getNeutralValue();
    bool found = false;
    for (int len = 1; from <= to;
         from = (from + 1) >> 1, to = (to - 1) >> 1, len <<= 1) {
      if ((from & 1) != 0) {
        resl = found ? queryOperation(resl, joinNodeValueWithDelta(from, len))
                     : joinNodeValueWithDelta(from, len);
        found = true;
      }
      if ((to & 1) == 0) {
        resr = found ? queryOperation(joinNodeValueWithDelta(to, len), resr)
                     : joinNodeValueWithDelta(to, len);
        found = true;
      }
    }
    int res = queryOperation(resl, resr);
    if (!found)
      ;
    return res;
  }
  void modify(int from, int to, int delta) {
    from += gn;
    to += gn;
    pushDelta(from);
    pushDelta(to);
    int a = from;
    int b = to;
    for (; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1) {
      if ((from & 1) != 0) {
        this->delta[from] = joinDeltas(this->delta[from], delta);
      }
      if ((to & 1) == 0) {
        this->delta[to] = joinDeltas(this->delta[to], delta);
      }
    }
    for (int i = a, len = 1; i > 1; i >>= 1, len <<= 1) {
      int k = i >> 1;
      value[k] = queryOperation(joinNodeValueWithDelta(k << 1, len),
                                joinNodeValueWithDelta((k << 1) | 1, len));
    }
    for (int i = b, len = 1; i > 1; i >>= 1, len <<= 1) {
      int k = i >> 1;
      value[k] = queryOperation(joinNodeValueWithDelta(k << 1, len),
                                joinNodeValueWithDelta((k << 1) | 1, len));
    }
  }
};
const int mn = (4e5) + 8;
int a[mn];
int vl[mn], vr[mn];
MinSegTree<mn> segmin;
int initdepth[mn];
void fdepth(int p, int L, int R, int d) {
  initdepth[p] = d;
  int pl = segmin.query(L, p - 1);
  int pr = segmin.query(p + 1, R);
  if (pl != segmin.identity.second) fdepth(pl, L, p - 1, d + 1);
  if (pr != segmin.identity.second) fdepth(pr, p + 1, R, d + 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) a[n + i] = a[i];
  {
    vector<pair<int, int> > v;
    v.push_back(make_pair(-INF, -1));
    for (int p = 0; p < 2 * n; p++) {
      int imin = 0, imax = v.size();
      while (imin < imax) {
        int imid = (imin + imax) / 2;
        if (v[imid].first < a[p])
          imin = imid + 1;
        else
          imax = imid;
      }
      v.resize(imin);
      vl[p] = v.back().second;
      v.push_back(make_pair(a[p], p));
    }
  }
  {
    vector<pair<int, int> > v;
    v.push_back(make_pair(-INF, 2 * n));
    for (int p = 2 * n - 1; p >= 0; p--) {
      int imin = 0, imax = v.size();
      while (imin < imax) {
        int imid = (imin + imax) / 2;
        if (v[imid].first < a[p])
          imin = imid + 1;
        else
          imax = imid;
      }
      v.resize(imin);
      vr[p] = v.back().second;
      v.push_back(make_pair(a[p], p));
    }
  }
  segmin.init(n);
  for (int p = 0; p < n; p++) {
    segmin[p] = make_pair(a[p], p);
  }
  segmin.build();
  {
    int p1 = segmin.query(0, n - 1);
    fdepth(p1, 0, n - 1, 0);
  }
  SegmentTreeFast segmax(2 * n);
  for (int p = 0; p < n; p++) {
    segmax.modify(p, p, initdepth[p]);
  }
  pair<int, int> ans = make_pair(segmax.query(0, n - 1), 0);
  for (int p = 0; p < n - 1; p++) {
    {
      int R = p + n - 1;
      int r = vr[p];
      segmax.modify(p + 1, min(R, r - 1), -1);
    }
    {
      int l = vl[p + n];
      int pdepth = 0;
      if (l > p) {
        pdepth = 1 + segmax.query(l, l);
      }
      segmax.modify(p + n, p + n, pdepth);
      segmax.modify(l + 1, p + n - 1, 1);
    }
    int cand = segmax.query(p + 1, p + 1 + n - 1);
    chkmin(ans, make_pair(cand, p + 1));
  }
  ans.first++;
  printf("%d %d\n", ans.first, ans.second);
}
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}