How to retrieve lost contacts after using Cleaner-App on iPhone?

Cleaner apps are unnecessary, are an absolute waste of money and can have unintended consequences. Remove it immediately. See this link and hope you can get them back --> Restore contacts stored in iCloud on iCloud.com - Apple Support

Not sure what all you have tried, however below are a few recommendations:

• Do you use iCloud for contacts? If Yes, then go to 👉 www.icloud.com and follow instructions here 👉 Contacts: Restore contacts stored in iCloud on iCloud.com 
• If you do not use iCloud for backups, then do you have a backup of your iPhone on a computer that was created before the contacts were deleted? If Yes, then you can 👉 Restore your iPhone from that computer backup.
• Did you, by any chance, remove an email account, from your iPhone, that was associated with those contacts? If Yes, then add that email account back to see whether the contacts return.

Axel F.