Maija is preparing for NCPC on the Aalto competitive programming course. She's been training hard and is shooting straight for task E Train Schedule. She's gotten an idea for a clever square-root trick, but is still getting a Time Limit exceeded. Help her find the fault in her code.

Input

• No input

Output

Your program should output a test case where Maija's solution fails.

Constraints (of your output)

• 1 \le n \le 10^5
• 1 \le a_i \le n

Maija's code

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n;
    cin >> n;

    vector<int> a(n), ans(n, 0);
    for(int &i : a) cin >> i;

    vector<bool> visited(n, 0);
    for(int i=0; i<n; i++){
        if(visited[i]) continue;
        if(a[i]*a[i] < n){
            vector<int> count(a[i], 0);
            for(int j=i, k=0; j<n; j++, k=(k+1)%a[i]){
                count[k] += a[i] == a[j];
                visited[j] = visited[j] | (a[i] == a[j]); 
                ans[j] += count[k];
            }
        } else {
            for(int j=i; j<n; j+=a[i]) ans[j]++;
        }
    }

    for(int i : ans) cout << i << ' ';

    return 0;
}