I recently tried to get my Indonesia visa in Tokyo, but the person flat out denied me. I was quite agitated, as I like to get visas in advance (especially when I must rush to get somewhere after the plane lands) but to help you out, I have gotten my visa on arrival thrice times at Soekarno-Hatta, and each time was less than five minutes. It was either $20 or $25 and you do not need a picture.