class Solution{
    public:
    // arr: input array
    // n: size of array
    //Function to rearrange an array so that arr[i] becomes arr[arr[i]]
    //with O(1) extra space.
    void arrange(long long v[], int n) {
        // Your code here
        for(int i= 0; i < n; i++){
            if(v[i] >= 0){
                int val = -v[i], ini = i, p = i;
                while( v[p] != ini){
                    int t = v[p];
                    v[p] = v[t];
        		    if(v[p] == 0)
        			    v[p] = INT_MIN;
        		    else
        			    v[p] *= -1;
            		p = t;
                }
                v[p] = val;
            }
        }
        for(int i= 0; i <n ;i++)
            if(v[i] != INT_MIN)
                v[i] *= -1;
            else
                v[i] = 0;
    }
};