Contact openings extending to sacrificial layers located at different depths can be formed by sequentially exposing a greater number of openings in a mask layer by iterative alternation of trimming of a slimming layer over the mask layer and an anisotropic etch that recesses pre-existing contact openings by one level. In one embodiment, pairs of an electrically conductive via contact and electrically conductive electrodes can be simultaneously formed as integrated line and via structures. In another embodiment, encapsulated unfilled cavities can be formed in the contact openings by non-conformal deposition of a material layer, electrically conductive electrodes can be formed by replacement of portions of the sacrificial layers, and the electrically conductive via contacts can be subsequently formed on the electrically conductive electrodes. Electrically conductive via contacts extending to electrically conductive electrodes located at different level can be provided with self-aligned insulating liner.