774_F. Pens And Days Of Week_10327
Stepan has n pens. Every day he uses them, and on the i-th day he uses the pen number i. On the (n + 1)-th day again he uses the pen number 1, on the (n + 2)-th — he uses the pen number 2 and so on.

On every working day (from Monday to Saturday, inclusive) Stepan spends exactly 1 milliliter of ink of the pen he uses that day. On Sunday Stepan has a day of rest, he does not stend the ink of the pen he uses that day. 

Stepan knows the current volume of ink in each of his pens. Now it's the Monday morning and Stepan is going to use the pen number 1 today. Your task is to determine which pen will run out of ink before all the rest (that is, there will be no ink left in it), if Stepan will use the pens according to the conditions described above.

Input

The first line contains the integer n (1 ≤ n ≤ 50 000) — the number of pens Stepan has.

The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is equal to the number of milliliters of ink which the pen number i currently has.

Output

Print the index of the pen which will run out of ink before all (it means that there will be no ink left in it), if Stepan will use pens according to the conditions described above. 

Pens are numbered in the order they are given in input data. The numeration begins from one. 

Note that the answer is always unambiguous, since several pens can not end at the same time.

Examples

Input

3
3 3 3


Output

2


Input

5
5 4 5 4 4


Output

5

Note

In the first test Stepan uses ink of pens as follows: 

  1. on the day number 1 (Monday) Stepan will use the pen number 1, after that there will be 2 milliliters of ink in it; 
  2. on the day number 2 (Tuesday) Stepan will use the pen number 2, after that there will be 2 milliliters of ink in it; 
  3. on the day number 3 (Wednesday) Stepan will use the pen number 3, after that there will be 2 milliliters of ink in it; 
  4. on the day number 4 (Thursday) Stepan will use the pen number 1, after that there will be 1 milliliters of ink in it; 
  5. on the day number 5 (Friday) Stepan will use the pen number 2, after that there will be 1 milliliters of ink in it; 
  6. on the day number 6 (Saturday) Stepan will use the pen number 3, after that there will be 1 milliliters of ink in it; 
  7. on the day number 7 (Sunday) Stepan will use the pen number 1, but it is a day of rest so he will not waste ink of this pen in it; 
  8. on the day number 8 (Monday) Stepan will use the pen number 2, after that this pen will run out of ink. 



So, the first pen which will not have ink is the pen number 2.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        long[] cnt;
        int n;
        long[] a;
        long[] b;

        boolean check(long day) {
            for (int i = 0; i < n; ++i) b[i] = a[i];
            long r = day / (7 * n);
            for (int i = 0; i < n; ++i) {
                b[i] -= r * cnt[i];
                if (b[i] <= 0) return true;
            }
            int mod = (int) (day % (7 * n));
            int th = 0;
            int id = 0;
            for (int i = 0; i < mod; ++i) {
                if (th != 6) {
                    b[id]--;
                    if (b[id] <= 0) return true;
                }
                th = (th + 1) % 7;
                id = (id + 1) % n;
            }
            return false;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            cnt = new long[n];
            a = new long[n];
            b = new long[n];
            for (int i = 0; i < n; ++i) a[i] = in.nextInt();
            int th = 0;
            int id = 0;
            for (int i = 0; i < n * 7; ++i) {
                if (th != 6) cnt[id]++;
                th = (th + 1) % 7;
                id = (id + 1) % n;
            }

            long lo = 1;
            long hi = (long) 1e17;
            long best = -1;
            while (lo <= hi) {
                long mid = (lo + hi) / 2;
                if (check(mid)) {
                    best = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            check(best);
            for (int i = 0; i < n; ++i)
                if (b[i] <= 0) {
                    out.println(i + 1);
                    break;
                }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}


5
5 4 5 4 4
 3
3 3 3
 2
1000000000 1000000000
 3
999999999 1000000000 1000000000
 4
1000000000 1000000000 1000000000 1000000000
 8
1000000000 999999999 1000000000 999999999 1000000000 999999999 999999999 999999999
 7
10 10 10 10 10 10 10
 2
999999999 999999999
 21
996 995 996 996 996 996 995 996 996 995 996 996 995 996 995 995 995 995 996 996 996
 5
999999999 1000000000 999999999 1000000000 999999999
 8
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 1
1
 28
2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033
 1
2
 1
1123
 7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 5
1000000000 1000000000 1000000000 1000000000 1000000000
 6
1000000000 999999999 999999999 999999999 1000000000 1000000000
 3
1000000000 1000000000 1000000000
 6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 4
999999999 999999999 999999999 999999999
 7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1
 28
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
 28
2033 2033 2034 2033 2034 2034 2033 2034 2033 2034 2033 2034 2034 2033 2033 2034 2034 2033 2034 2034 2034 2033 2034 2033 2034 2034 2034 2034
 1
1000000000
 7
1000000000 1000000000 1000000000 1000000000 999999999 999999999 999999999
 2
1010000000 1000000000
 3
999999999 1000000000 1000000010
 21
996 995 996 996 996 996 995 996 996 995 996 451 995 996 995 995 995 995 996 996 996
 6
1000000000 999999999 999999999 999999999 1000000000 1000100000
 6
1000000000 1000000000 1001000000 1000000000 1000000000 1000000000
 7
1000000000 1000000000 1000000000 1000000000 999999999 1280916009 999999999
 28
2033 2033 2034 2033 2162 2034 2033 1988 2033 2034 2033 2034 2034 2033 2033 2034 2034 2033 2034 2034 2034 2033 2034 2033 2034 2034 2034 2034
 28
2033 2033 2034 2033 2162 2034 2033 1988 2033 2034 2033 2034 2034 2033 2033 2034 2034 2033 872 2034 2034 2033 2034 2033 2034 2034 2034 2034
 28
3171 2033 2033 2033 2033 1074 2033 2033 2033 2033 2033 3122 2033 2033 2033 2033 2033 2033 2033 2033 2918 2033 2033 2033 2033 2171 2033 2033
 28
3171 2033 2321 2033 2033 1074 2033 2033 3636 2033 2033 3122 2033 2033 2033 2033 2033 2033 2033 2033 2918 2033 2033 986 2033 2171 2033 2033
 21
996 995 1074 996 1712 996 995 1821 390 995 996 451 995 1636 995 995 1104 995 996 996 996
 4
1000000000 1000000000 1000000001 1000000000
 8
1010000000 999999999 1000000000 999999999 1000000000 999999999 999999999 999999999
 7
8 10 10 10 10 10 10
 2
470670031 999999999
 5
999999999 1000000000 999999999 1100000000 999999999
 8
1000000000 1000000000 1000000001 1000000000 1000000000 1000000000 1000000000 1000000000
 28
3171 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033
 1
4
 1
1038
 7
1000000000 1000000000 1000000100 1000000000 1000000000 1000000000 1000000000
 5
1000000000 1000000000 1000010000 1000000000 1000000000
 3
1000000000 1000000000 1100000000
 7
1000001000 1000000000 1000000000 1000000000 1000000000 1000000000 1
 28
1000 1000 1000 1000 1000 1000 1000 1010 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
 28
2033 2033 2034 2033 2162 2034 2033 2034 2033 2034 2033 2034 2034 2033 2033 2034 2034 2033 2034 2034 2034 2033 2034 2033 2034 2034 2034 2034
 1
1001000000
 5
5 4 5 4 5
 3
3 3 4
 2
1010100000 1000000000
 3
999999999 1000001000 1000000010
 4
1000000000 1000000000 1000100001 1000000000
 7
8 10 15 10 10 10 10
 2
470670031 1136281459
 21
996 995 996 996 996 996 995 996 1581 995 996 451 995 996 995 995 995 995 996 996 996
 8
1000100000 1000000000 1000000001 1000000000 1000000000 1000000000 1000000000 1000000000
 28
3171 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2171 2033 2033
 1
6
 1
282
 7
1000000000 1000000000 1000000101 1000000000 1000000000 1000000000 1000000000
 5
1000000100 1000000000 1000010000 1000000000 1000000000
 3
1000100000 1000000000 1100000000
 6
1000000000 1000000000 1001000000 1001000000 1000000000 1000000000
 7
1000001000 1000010000 1000000000 1000000000 1000000000 1000000000 1
 28
1000 1001 1000 1000 1000 1000 1000 1010 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
 1
1001000001
 7
1000000000 1000000000 1000000000 1000000000 1021644953 1280916009 999999999
 5
5 4 5 4 9
 3
3 5 4
 2
1000100000 1000000000
 3
341966162 1000001000 1000000010
 4
1000000000 1000000000 1000100001 1000010000
 7
8 10 15 10 10 8 10
 21
996 995 996 996 996 996 995 1821 1581 995 996 451 995 996 995 995 995 995 996 996 996
 8
1000100000 1000000000 1000000001 1000000000 1000000000 1000000000 1000000000 1010000000
 28
3171 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 2918 2033 2033 2033 2033 2171 2033 2033
 1
10
 1
212
 7
1000000000 1000000000 1000000101 1000000000 1000000000 1000010000 1000000000
 5
1000000100 1000000000 1001010000 1000000000 1000000000
 3
1000100000 1001000000 1100000000
 6
1000000000 1000000000 1001000100 1001000000 1000000000 1000000000
 7
1000001000 1000010000 1000000000 1000000000 1001000000 1000000000 1
 1
0001000001
 7
1000000000 1000000010 1000000000 1000000000 1021644953 1280916009 999999999
 5
5 4 7 4 9
 3
3 5 5
 2
1000110000 1000000000
 3
341966162 1000001100 1000000010
 4
1000000000 1000000001 1000100001 1000010000
 7
8 10 23 10 10 8 10
 21
996 995 996 996 996 996 995 1821 1581 995 996 451 995 1246 995 995 995 995 996 996 996
 8
1000100000 1000000000 1000000001 1000001000 1000000000 1000000000 1000000000 1010000000
 28
3171 2033 2033 2033 2033 2033 2033 2033 2033 2033 2033 3122 2033 2033 2033 2033 2033 2033 2033 2033 2918 2033 2033 2033 2033 2171 2033 2033
 1
14
 1
106
 5
1100000100 1000000000 1001010000 1000000000 1000000000
 3
1000100000 1101000000 1100000000
 6
1000000000 1000000000 1001000100 1001001000 1000000000 1000000000
 7
1000001000 1000010000 1000000000 1000000000 1001000000 1000000000 2
 28
2033 3612 2034 2033 2162 2034 2033 1988 2033 2034 2033 2034 2034 2033 2033 2034 2034 2033 872 2034 2034 2033 2034 2033 2034 2034 2034 2034
 1
0101000001
 7
1000000000 1000000010 1000000000 1000000000 1545741034 1280916009 999999999
 5
5 4 7 4 2
 3
3 1 5
 2
1000110000 1000001000
 3
341966162 1000001100 1000000110
 4
1000000000 1000000001 1010100001 1000010000
 7
8 10 23 10 10 14 10
 21
996 995 996 996 996 996 995 1821 1581 995 996 451 995 1636 995 995 995 995 996 996 996
 8
1000100000 1000000000 1001000001 1000001000 1000000000 1000000000 1000000000 1010000000
 1
8
 1
70
 3
1000100100 1101000000 1100000000
 6
1000000000 1000000000 1001000100 1001001000 1000000000 1000001000
 7
1000001000 1000010000 1000000000 1000000000 1001000000 1010000000 2
 28
2033 3612 2034 2033 2162 2034 2033 1988 2033 2034 2033 2034 1331 2033 2033 2034 2034 2033 872 2034 2034 2033 2034 2033 2034 2034 2034 2034
 1
0101001001
 5
5 4 4 4 2
 3
2 1 5

5
 2
 2
 1
 1
 2
 1
 1
 2
 1
 1
 1
 1
 1
 1
 1
 1
 3
 2
 4
 1
 1
 1
 1
 1
 5
 2
 1
 12
 3
 4
 5
 8
 19
 6
 24
 9
 1
 2
 1
 1
 1
 1
 2
 1
 1
 1
 1
 2
 2
 1
 1
 1
 2
 2
 2
 1
 1
 1
 1
 12
 2
 2
 1
 1
 1
 5
 2
 5
 3
 1
 1
 1
 2
 1
 2
 1
 1
 1
 12
 2
 2
 1
 1
 1
 5
 1
 5
 3
 1
 1
 2
 1
 2
 1
 1
 1
 12
 2
 2
 1
 1
 5
 1
 5
 3
 19
 1
 1
 5
 2
 2
 1
 1
 1
 12
 2
 1
 1
 1
 5
 3
 19
 1
 5
 2
