It was recently found that oxygen induces ordered reconstructions on several III-V surfaces. The most oxygen-rich reconstruction shows (3x1) periodicity. Based on first-principles investigations, a detailed atomic model is presented for this reconstruction. The uncommon periodicity is attributed to the highly stable In - O - In trilayer below surface which also leads to stabilizing additional bonds within the surface layer. The strain induced by the trilayer is more effectively accommodated within the (3 x 1) reconstruction than within the competing (2 x 1) reconstruction due to smaller number of dimers. It is proposed that the experimentally found semiconductivity is reached by substitutional atoms within the surface layer. Suitable substitution preserves the magnitude of the bulk band gap.