Far off from the outskirts of the city lies a village name Hirambarpur where n saints reside. One fine day, devils attacked the beautiful village. As a result, all the n saints came together to organize a ritual to stop the evil demons.

All the saints are sitting in a circle, starting from position 1 to n, each reciting his own chant. Each saint takes his own time to recite his chants. One of the demons , who is a good demon, starts at a random saint and starts killing the saints one by one in clockwise. When he starts killing the saints, the ith saint needs ti more time to complete his chant. Killing each saint requires 1second. Since he kills the saints one by one, the remaining saints get some extra time to complete their chants. That is, if he starts at xth saint, then x+1th saint will get 1s extra time, x+2 will get 2s, and so on. In this way it is possible that a few saints complete their chants and be safe.

Given n saints and the time remaining to complete their chant, what is the position from which the good demon should start killing the saints so that maximum saints are able to complete their chants?

Input:

The first line of each input consists of n, denoting the number of saints.

The next line contains n integers, where the ith integer represents the time required by the ith saint to complete his chant.

Constraints:

1<=n<=10^5

1<=ti<=n

Output:

Output the position from which the demon should start so as to maximize the number of saints completing their chants.