There are a few different ways to regain access to a Google Account. Make sure that you investigate all of them. If you've not provided an alternate email address or a phone number you may be out of luck though.
sod :
More seriously, all my services use a same long password, which recorded on paper disappeared
I very, very highly recommend that you avoid reusing your password for everything (ideally you wouldn't reuse it at all). If one service is compromised and someone manages to get access to your password then
all of your services are compromised. In your case, someone need only find your piece of paper.