#!/usr/bin/perl

use strict;
use warnings;

use XML::Twig;

my $twig_to_del=XML::Twig->new(
                        twig_handlers=>{
                                        #to_delete elements
                                        '/document/header'=>\&element_delete,
                                        },
                        )
                         ->parse(\*DATA)
                         ->print;

sub element_delete
{
  my ($twig, $element)= @_;
  my $first_header= $element->prev_sibling( 'header');
  if( $first_header && ! $first_header->att( '#header_deleted'))
    { $element->delete;
      $first_header->set_att( '#header_deleted' => 1);
    }
}

__DATA__
<document>
  <header>h1</header>
  <header>h2</header>
  <header>h3</header>
</document>