```
int j = 0;
for(int i = 0; i < n; ++i) {
while(j < n && arr[i] < arr[j]) {
j++;
}
}
```

still not convinced by the solution as it is nested loop so inner while loop will run atmost n times and outer loop also runs for n times so overall complexity should be O(n*n).