Background

Special for beginners, ^_^

Description

n个小朋友站成一排，每个小朋友提前（为了公平起见，不能一边淘汰一边写数字提交）写好一个数提交给石老师，从第1个小朋友开始报数1，如果报数到了末尾就从排头接着往下报，报到第1个小朋友写的数字的那个小朋友惨遭淘汰。淘汰的下一位小朋友接着报数1，报到该小朋友的数字的小朋友又惨遭淘汰。如此进行n-1轮，直到最后剩下一个小朋友就是天选之人。正所谓谋事在人，成事在天，请输出最后的幸运星在最开始队伍中的序号（从1开始计数）。

Format

Input

第一行输入一个正整数n(2<=n<=1e4)，表示小朋友的总数。下一行输出每个小朋友的数字ki（不超过1e6），表示淘汰者的报数序号。

Output

幸运之星的编号（从1开始计数）。

Samples

4
8 2 4 2

3

Limitation

1s, 1024KiB for each test case.