If the phone was lost, unless the contacts were synced to say a google account, they are gone. The only way to 'possibly' get any info back would be phone numbers alone. Most carriers/service providers have in your online account, access to incoming and outgoing calls, as well as texts sent. Not the calls themselves or the texts, but the numbers called. Granted there are no names attached, only dates, times, and length of call, but you may be able to get some of the numbers that way.